Word Break

Medium

Python

def word_break(s,wordDict):
    words=set(wordDict); dp=[False]*(len(s)+1); dp[0]=True
    for i in range(1,len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in words: dp[i]=True; break
    return dp[len(s)]

Java

public boolean wordBreak(String s,List<String> wordDict){
    Set<String> words=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]&&words.contains(s.substring(j,i))){
                dp[i]=true; break;
            }
    return dp[s.length()];
}

Key Insight

Python slice s[j:i] vs Java substring(j,i).

Python → Java Differences

set(wordDict) vs new HashSet<>()
s[j:i] vs substring(j,i)
Boolean DP identical

Python

def word_break(s,wordDict):
    words=set(wordDict); dp=[False]*(len(s)+1); dp[0]=True
    for i in range(1,len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in words: dp[i]=True; break
    return dp[len(s)]

Java

public boolean wordBreak(String s,List<String> wordDict){
    Set<String> words=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]&&words.contains(s.substring(j,i))){
                dp[i]=true; break;
            }
    return dp[s.length()];
}

Algorithm Steps

1. dp[i] = can break s[:i]
2. Try all split points

← Previous All Dynamic Programming Next →