Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Test Cases
Input:
(String) s = "leetcode"
(String[]) wordDict = ["leet","code"]
Output:
(boolean) true
Input:
(String) s = "applepenapple"
(String[]) wordDict = ["apple","pen"]
Output:
(boolean) true
Explanation
Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
Input:
(String) s = "catsandog"
(String[]) wordDict = ["cats","dog","sand","and","cat"]
Output:
(boolean) false
Solution
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.length();
vector<bool> dp(n, false);
for(int i=0; i<n; i++) {
for(int j=0; j<=i; j++) {
string sub = s.substr(j, i-j+1);
if (contains(wordDict, sub) && (j==0 || dp[j-1])) {
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
bool contains(vector<string> &v, string s) {
return find(v.begin(), v.end(), s) != v.end();
}
};class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null || s.length() == 0) return false;
int n = s.length();
Set<String> dict = new HashSet<>(wordDict);
// dp[i] represents whether s[0...i] can be formed by dict
boolean[] dp = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
String sub = s.substring(j, i + 1);
if (dict.contains(sub) && (j == 0 || dp[j - 1])) {
dp[i] = true;
break;
}
}
}
return dp[n - 1];
}
}class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp, st = [False]*n, set(wordDict)
for i in range(n):
for j in range(i+1):
if s[j:i+1] in st and (j==0 or dp[j-1]):
dp[i] = True
break
return dp[n-1]