Java DP solution 2ms


  • 0
    O
    public final boolean wordBreak(final String s, final Set<String> wordDict) {
            if (s == null || s.isEmpty()) {
                return true;
            }
            int n = s.length(), min = n, max = 0;
            for (String str : wordDict) {
                min = Math.min(min, str.length());
                max = Math.max(max, str.length());
            }
    
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            
            for (int i = min; i <= n; i++) {
                int start = Math.max(0, i - max);
                for (int j = start; j <= i - min; j++) {
                    if (dp[j]) {
                        String sub = s.substring(j, i);
                        if (wordDict.contains(sub)) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
    
            return dp[n];
        }
    

Log in to reply
 

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