Java DP Solution using a boolean array


  • 0
    C
       public boolean wordBreak(String s, Set<String> wordDict) {
            if(s==null || wordDict==null)
                return false;
            boolean[] arr = new boolean[s.length()+1];
            for(int i=1; i<arr.length; i++){
                String temp1 = s.substring(0,i);
                if(!arr[i] && wordDict.contains(temp1)) arr[i]=true;
                if(arr[i]){
                    for(int j=i+1; j<arr.length; j++){
                        String temp2 = s.substring(i,j);
                        if(arr[j]==false && wordDict.contains(temp2)) arr[j]=true;
                        if(j==arr.length-1 && arr[j]) return true;
                    }
                }
            }
            return arr[arr.length-1];
        }

  • 0
    P

    how can we fetch the real string with space separation from the boolean array? Is it possible?


Log in to reply
 

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