Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s = "leetcode", dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
Solution:
Need to use DP because derictly loop through the string may not return the correct answer.
Test case: s="aaaaaaa", dict = ["aaa", "aaaa"]
Two solutions:
First Dynamic programming:
dp[0] = true;// always true, because empty string can always add space to it.
dp[1] = dp[0]&&dict.Contains(s.Substring(0, 1);
dp[2] =( dp[1]&&dict.Contains(s.Substring(1,1))) ||(dp[0]&& dict.Contains(s.Substring(0,2)));
so need to loop through dp[j]&&wordDict.Contains(s.Substring(j,i-j)) untill dp[i] is true where j from 0 to i;
public class Solution {
public bool WordBreak(string s, ISet<string> wordDict)
{
ISet<int> set = new HashSet<int>();
if(string.IsNullOrEmpty(s))
{
return true;
}
int l = s.Length;
bool[] dp = new bool[l+];
dp[] = true;
for(int i=; i<l+; i++)
{
for(int j=; j<i; j++)
{
dp[i]=dp[j]&&wordDict.Contains(s.Substring(j,i-j));
if(dp[i])
{
break;
}
}
}
return dp[l];
}
}
Second DFS:
Use recursion in Dfs to mark the indexes those already looped through and returned false;
public class Solution {
public bool WordBreak(string s, ISet<string> wordDict)
{
ISet<int> set = new HashSet<int>();
return Dfs(s, , wordDict, set);
}
private bool Dfs(string s, int index, ISet<string> dict, ISet<int> set)
{
// base case
if (index == s.Length) return true;
// check memory
if (set.Contains(index)) return false;
// recursion
for (int i = index + ; i <= s.Length; i++)
{
String t = s.Substring(index, i-index);
if (dict.Contains(t))
if (Dfs(s, i, dict, set))
return true;
else
set.Add(i);
}
set.Add(index);
return false;
}
}