Simple Java Solution


  • 0
    Z
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;
    
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] dp = new boolean[s.length() + 1];
            int minLen = Integer.MAX_VALUE;
            int maxLen = Integer.MIN_VALUE;
            for (String word : wordDict) {
                minLen = Math.min(minLen, word.length());
                maxLen = Math.max(maxLen, word.length());
            }
    
            dp[0] = true;
            for (int i = minLen; i <= s.length(); i++) {
                int j = i - maxLen < 0 ? 0 : i-maxLen;
                for (; j <= i-minLen; j++) {
                    if (dp[j] && wordDict.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
    
            return dp[s.length()];
        }
     
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.