Skip to content

Instantly share code, notes, and snippets.

@bobfang1992

bobfang1992/word_break.java

Last active January 10, 2021 00:42
Show Gist options
  • Save bobfang1992/db05b36e80f5c48fb2e56ac7011c72ba to your computer and use it in GitHub Desktop.
Save bobfang1992/db05b36e80f5c48fb2e56ac7011c72ba to your computer and use it in GitHub Desktop.
Download ZIP
mock_interview_3
Raw
word_break.java
/*
s = "applepenapple" dictionary = ["apple", "pen"]
s = "apple" + "pen" + "apple"
return True
s = "appplepearapple" dictionary = ["apple", "pen"]
return False
0 <= len(s) <= 10^5
0 <= len(dictonary) <= 10^5
*/
// dp[i] should be the result of the this problem for s[0:i]
// i, j j <= i; dp[j] && set.contains(j, i)
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for (int i = 0; i < wordDict.size(); i++) {
set.add(wordDict.get(i));
}
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j <= i; j++) {
dp[i] = dp[j] && set.contains(s.substring(j, i));
if (dp[i]) {
break;
}
}
}
return dp[s.length()];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment