Simple JAVA DP 2ms Solution


  • 0
    B
    public class Solution {
        //function that returns the maxlength of all the strings in set 
         private int getMaxLength(Set<String> dict) {
            int maxLength = 0;
            for (String word : dict) {
                maxLength = Math.max(maxLength, word.length());
            }
            return maxLength;
        }
        public boolean wordBreak(String s, Set<String> wordDict) {
            int len = s.length();
            if(len==0)return false;
            int maxLen = getMaxLength(wordDict);
            //the memo array 
            boolean[] memo = new boolean[len+1];
            //base case
            memo[0] = true;
            if(wordDict.contains(s.substring(0,1)))memo[1]=true;
            //Iteration
            for(int i = 2;i <= len;i++){
                for(int j = Math.max(0,i - maxLen); j < i;j++){
                     if(memo[j]==false)continue;
                     String cur = s.substring(j,i);
                     if(wordDict.contains(cur)){
                         memo[i] = true;
                     }
                }
            }
            return memo[len];
        }
    }
    

Log in to reply
 

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