Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
EDGE CASE
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a DP Array to check if any substring from i -> j is in the word bank. Build up this solution to the last index of the input string.
1) Construct a boolean array of size N + 1 as a DP tool
2) Set the first index to True
- This means there is a valid substring up until that index (exclusive)
3) Iterate from 0 -> N as variable i
a) If the current index, i, in the DP boolean array is True we iterate from
i -> N as variable j
i) If the substring input[i:j] is within the word bank, we mark DP[j] as true
- This signifies the substring of the input from 0 -> j (exlusive) is valid
b) Continue to build the solution to the end
4) The boolean value of the last index signifies whether the input string can
be broken
⚠️ Common Mistakes
Some people may miss how there are invalid paths that ‘trick’ their program down a certain path while there were also other valid words in the bank. Usually, this is due to premature matching and no ‘recursive’ efforts.
Implement the code to solve the algorithm.
def wordBreak(self, word: str, wordList: List[str]) -> bool:
wordSet = set(wordList) #O(M)
dp = [True] + [False] * len(word)
for i in range(len(word)): # O(N)
if dp[i]:
for j in range(i + 1, len(word) + 1): # O(N)
if word[i:j] in wordSet: # O(N) String Generation
dp[j] = True
return dp[-1]
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
n is the length of the input string.