Dynamic Programming Java solution


  • 4
    V

    public class Solution {

    public boolean wordBreak(String s, Set<String> dict) {

       if(s.length() == 0){
           return true;
       }
       if(dict == null){
           return false;
       }    
        
        
        int n = s.length();
        boolean[] d = new boolean[n+1];
        d[0] = true;
        for(int m = 1; m < n; m++){
            d[m] = false;
        }
        
       
        
        for(int i = 1; i < n+1; i++){
            for(int j = 0; j < i; j ++){
                if(d[j] && dict.contains(s.substring(j, i))){
                    d[i] = true;
                    break;
                }
            }
        }
        
        
        return d[n];
    }
    

    }


Log in to reply
 

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