Word Break — Reachability DP
Sanjeev SharmaAdvertisement
Problem
Given string s and wordDict, return true if s can be segmented into dict words.
Approach — Reachability DP
dp[0]=True. For each i: if any j where dp[j] is True and s[j:i] in dict, set dp[i]=True.
Time: O(n² * m) where m = avg word len | Space: O(n)
Solutions
Python
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
words=set(wordDict); n=len(s)
dp=[False]*(n+1); dp[0]=True
for i in range(1,n+1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i]=True; break
return dp[n]
C++
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict){
unordered_set<string> words(wordDict.begin(),wordDict.end());
int n=s.size(); vector<bool> dp(n+1,false); dp[0]=true;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(dp[j]&&words.count(s.substr(j,i-j))){dp[i]=true;break;}
return dp[n];
}
};
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict){
Set<String> words=new HashSet<>(wordDict);
int n=s.length(); boolean[] dp=new boolean[n+1]; dp[0]=true;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(dp[j]&&words.contains(s.substring(j,i))){dp[i]=true;break;}
return dp[n];
}
}
Complexity
- Time: O(n² * m) | Space: O(n)
Advertisement
