[Leetcode] 139.

제목.
비어 있 지 않 은 문자열 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

사고 분석.
폭력 수색
이 문 제 는 처음에 우리 가 생각 한 것 은 모든 문 자 를 옮 겨 다 니 며 워드 Dict 안에 있 는 지 아 닌 지 를 보 는 것 이 분명 하 다.한편, wordDict 는 list 입 니 다. 찾기 는 o (N) 의 시간 복잡 도 입 니 다. 이 시간 복잡 도 를 먼저 낮 추고 set 로 매번 찾 는 시간 복잡 도 를 o (1) 로 낮 춰 야 합 니 다.
하나의 문자열 을 어떻게 check 하 는 지 wordDict 가 구 성 될 수 있 는 지, 하나의 소박 한 생각 은 모든 문자열 을 두 단락 으로 나 누 어 재 귀 하 는 것 입 니 다.예 를 들 어 다음 과 같은 코드.

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        return helper(s, new HashSet<>(wordDict), 0);
    }
    public boolean helper(String s, Set 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)) 
                && helper(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

분명히 이런 사고방식 은 통 하지 않 는 다. 왜냐하면 시간 복잡 도가 너무 높 기 때문에 흥미 가 있 는 학생 들 이 한번 해 볼 수 있다.

시간 복잡 도: O (n ^ n)

공간 복잡 도: O (n)

기억 화 검색
반복 계산 이 너무 많다.어디 가 중복 됐어 요?예 를 들 어:

  : s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
for    ：
    : s = 'A' + helper('AAleetcodeB'),        ;
    : s = 'AA' + helper('AleetcodeB'),        ;
    : s = 'AAA' + helper('leetcodeB'),        ;

발견 되 었 습 니까? 위 에서 매번 반복 적 으로 계산 하 였 습 니 다 helper('leetcodeB').
시간 을 절약 하 는 방법 도 자 연 스 러 웠 다. 우리 가 검색 한 내용 을 기록 할 수 있 었 으 면 좋 겠 다.기억 에는 참고 할 수 있 는 두 가지 방법 이 있다.

동태 계획

기억 화 배열 검색

동적 계획
우 리 는 먼저 동태 계획 을 보고 동태 계획 은 사실 이해 하기 쉬 우 며 가장 중요 한 것 은 상태 전이 방정식 이다.모 르 는 학생 은 수 동 으로 모 의 하면 기본적으로 이해 할 수 있다.

dp [i] 는 [0, i] 하위 문자열 이 wordDict 로 구 성 될 수 있 는 지 여 부 를 나타 낸다

dp [i] = 임의의 j 에 대해 dp [j] & & wordDict 는 s [j + 1, i] 를 포함 하 는데 그 중에서 j 는 구간 [0, i] 에 속한다.

동적 계획 을 모 의 하 는 과정 은:

  : s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
dp[0] = true //    .
  dp: dp[1] = true, wordDict   'A';
  dp: dp[2] = true, 
        dp[1] = true, wordDict   'A';
  dp: dp[3] = true,
        dp[1] = true, wordDict   'AA';
...
    dp: dp[12] = false,
        dp[1]= true wordDict    'AAleetcodeB';
        dp[2]= true wordDict    'AleetcodeB';
        dp[3]= true wordDict    'leetcodeB';
        dp[7]= true wordDict    'codeB';
        dp[11]= true wordDict    'B'
         ,dp[12] = false.

자바 버 전 코드 는 다음 과 같 습 니 다:

class Solution {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null) return false;
        Set wordSet = new HashSet<>();
        for (int i = 0; i < wordDict.size(); i++) {
            wordSet.add(wordDict.get(i));
        }
        boolean[] dp = new boolean[s.length() + 1];
        //     
        dp[0] = true;
        // dp[i]        i      
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                String current = s.substring(j, i);
                if (dp[j] && wordSet.contains(current)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

시간 복잡 도: O (n ^ 2).2 층 for 순환.

공간 복잡 도: O (n).dp 배열 길 이 는 n 입 니 다.

DFS
동적 계획 과 기억 화 검색 은 모두 자주 사용 되 는 해법 입 니 다. 이 문 제 는 하나의 배열 memoToEndContain 로 위치 i 를 기록 하고 문자열 이 끝 날 때 까지 wordDict 로 구성 할 수 있 습 니까?아니면 우리 의 첫 번 째 예:

  : s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
  for  : 'A'     wordDict  
        'AA'     wordDict  
        ...
        'AAAleetcodeB'     wordDict  
               ：
              'A'      'A',      'A' ...          wordDict  ;

자바 코드:

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null) return false;
        Set wordSet = new HashSet<>(wordDict);
        //    i            .
        Boolean[] memoToEndContain = new Boolean[s.length()];
        return dfs(s, 0, wordSet, memoToEndContain);
    }

    public boolean dfs(String s,
                       int start,
                       Set wordSet,
                       Boolean[] memoToEndContain) {
        //      .
        if (start == s.length()) {
            return true;
        }
        //        .
        if (memoToEndContain[start] != null) {
            return memoToEndContain[start];
        }

        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) 
                && dfs(s, end, wordSet, memoToEndContain)) {
                return memoToEndContain[start] = true;
            }
        }
        memoToEndContain[start] = false;
        return memoToEndContain[start];
    }
}

시간 복잡 도: O (n ^ 2).검색 트 리 의 크기 는 최대 n ^ 2 에 달 합 니 다.

공간 복잡 도: O (n).깊이 우선 이 진 트 리 의 깊이 는 n 입 니 다.