비어 있지 않은 문자열 s와 비어 있지 않은 단어 목록을 포함하는 사전 wordDict를 지정하여 s가 빈칸에서 한 개 이상의 사전에 나오는 단어로 분할될 수 있는지 여부를 판정합니다.
설명: 분할할 때 사전의 단어를 반복해서 사용할 수 있습니다.
너는 사전에 중복된 단어가 없다고 가정할 수 있다.

   1：

  : s = "leetcode", wordDict = ["leet", "code"]
  : true
  :    true    "leetcode"        "leet code"。
   2：

  : s = "applepenapple", wordDict = ["apple", "pen"]
  : true
  :    true    "applepenapple"        "apple pen apple"。
                    。
   3：

  : s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
  : false

분석하다.

처음에는 KMP 폭력과 유사한 방법으로 s를 모직으로, wordDict의 단어마다 하위직으로 하고,s가 끝까지 일치하는 경우(하지만 모직이 aaaaaa이고 자직이 있는wirdDic={"aaaaa", "aa"}와 같은 형식의 일치하는 경우는 정확한 결과는 일치할 수 있지만 매번 먼저 aaaaaa로 일치하는 경우 마지막 aa를 모직으로 보충할 수 없기 때문에 이전에 선택한 폭력을 후회할 수 있는 방법이 필요하므로 아래의 검색을 사용하십시오!)

방법1: 폭력 검색

class Solution {
    public  boolean wordBreak(String s, List wordDict) {
        return word_Break(s, wordDict, 0);
    }
    public  boolean word_Break(String s, List wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end)) {
                return true;
            }
        }
        return  false;
    }
}

기억형 검색(최적화)

public static boolean wordBreak(String s, List wordDict) {
        Boolean[] mem = new Boolean[s.length()+2];
        return word_Break(s, wordDict, 0,mem);
    }
    public static boolean word_Break(String s, List wordDict, int start,Boolean[] mem) {
        if (start == s.length()) {
            return true;
        }
        if (mem[start] != null) {
            return mem[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, mem)) {
                return mem[end] = true;
            }
        }
        return mem[start] = false;
    }

 

메서드2: DP

public static boolean wordBreak(String s, List wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 2];
        dp[0] = true;
        for(int i = 1 ;i <= len;i++){
            for(int j = 0;j < wordDict.size();j++) {
                if( i >= wordDict.get(j).length() && s.substring(i-wordDict.get(j).length(),i).contains( wordDict.get(j)) ) {
                    dp[i] = dp[i] || dp[i - wordDict.get(j).length()];
                }
            }
        }
        return dp[len];
        //return word_Break(s, wordDict, 0);
    }