Java 5 ms beats 98%


  • 1

    Last year, I failed one vital onsite because of this problem when I did not know dp. I even dreamed of it in my nightmare. Good to get over it.

    public boolean wordBreak(String s, List<String> wordDict) {
            int n = s.length();
            Set<String> dict = new HashSet<>();
            int maxLen = 0;
            for(String word : wordDict) {
                maxLen = Math.max(maxLen, word.length());
                dict.add(word);
            }
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            for(int i = 0; i < n; i++) {
                if(dp[i]) {
                    for(int j = i + 1; j <= n && j - i <= maxLen; j++) {
                        if(dict.contains(s.substring(i, j)) ) {
                            dp[j] = true;
                        }
                    }
                }
            }
            return dp[n];
        }

Log in to reply
 

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