Java Optimized Dp Solution (beats 93.39%)


  • 0

    Magic here is to find the string with max length in dictionary.

    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s.length() == 0) {
                return true;
            }
            if (wordDict.isEmpty()) {
                return false;
            }
            int maxLen = Integer.MIN_VALUE;
            for (String str : wordDict) {
                maxLen = Math.max(maxLen, str.length());
            }
            boolean[] can = new boolean[s.length() + 1];
            can[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                can[i] = false;
                for (int j = i; j >= 0 && i - j <= maxLen; j--) {
                    if (can[j] && wordDict.contains(s.substring(j, i))) {
                        can[i] = true;
                        break;
                    }
                }
            }
            
            return can[s.length()];
        }
    }
    

Log in to reply
 

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