Short and easy understood DP solution


  • 0
    W

    public class Solution {

    public boolean wordBreak(String s, Set<String> wordDict){
        boolean[] valid = new boolean[s.length()]; //init value are false;
        for(int i = 0; i < s.length(); ++i)
            for(String word : wordDict)
                if(word.length() <= i + 1 && word.compareTo(s.substring(i - word.length() + 1, i + 1)) == 0 && (i - word.length() + 1 == 0 || valid[i - word.length()]))
                    {valid[i] = true; break;}//break here can save some time
        return valid[s.length() - 1];
    }
    

    }


Log in to reply
 

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