Java with DP


  • 0
    F

    ...

    public class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            wordDict.sort(new Comparator<String>() {
                public int compare(String left, String right) {
                    return right.length() - left.length();
                }
            });
            return isWordCanBreak(s, 0, wordDict);
        }
    
    private boolean isWordCanBreak(String s, int index, List<String> wordDict) {
        List<String> canBreakList = new ArrayList<String>();
        for (String word : wordDict) {
            if (index + word.length() > s.length()) {
                continue;
            }
            boolean alreadyBreaked = false;
            for (String breakList : canBreakList) {
                if (breakList.endsWith(word)) {
                    alreadyBreaked = true;
                    break;
                }
            }
            if (alreadyBreaked) {
                continue;
            }
            String subString = s.substring(index, index + word.length());
            if (subString.equals(word)) {//匹配当前word
                if (index + word.length() == s.length()) {
                    return true;
                } else {
                    canBreakList.add(word);
                    if ( isWordCanBreak(s, index + word.length(), wordDict)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    

    }
    ...


Log in to reply
 

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