139. Word Break

📜 문제

• 문자열 `s`, 단어 사전 `wordDict`가 주어짐
• wordDict에 있는 단어들로 s를 분할할 수 있는지 확인 (≒ 단어들로 s를 만들 수 있는지 확인)
• wordDict내의 단어들은 여러번 재사용 가능

---

생각 하기

40분 정도 고민하다가 답을 봤다.

나는 단어 사전에 있는 단어들의 첫글자를 key로 하여 Map에 저장 하여 접근하도록 했다.

예시) wordDict =[cats, sand, dog, and, cat]
Map: [a - and], [c - cat, cats], [d - dog ], [s- sand]

dfs를 이용하여 접근했지만, 시간초과에 걸려서 틀렸다. (∵ 중복 탐색)

이 문제를 풀기 위해선, 이전 값의 결과를 저장해 중복 탐색을 하지 않도록 `memoization`을 이용해야한다.

`DFS` 와 `DP`, 이 두 가지 방법으로 풀 수 있다.

---

🍳 전체 소스 코드

class Solution {
     static int maxlen;
    public boolean wordBreak(String s, List<String> wordDict) {
      Map<String, Boolean> map = new HashMap<>();
        Set<String> wordSet = new HashSet<>(wordDict);
        maxlen=0;
        for(String word: wordDict) {
            maxlen = Math.max(maxlen, word.length());
        }

        return dfs(s, map, wordSet);
    }
     public static boolean dfs(String s, Map<String, Boolean> memo, Set<String> wordSet) {
        if(memo.containsKey(s)) return memo.get(s);
        if(wordSet.contains(s)) return true;

        for(int i=1;i<s.length();i++) {
            String prefix = s.substring(0,i);
            if(prefix.length()>maxlen){
                break;
            }
            if(wordSet.contains(prefix) && dfs(s.substring(i), memo, wordSet)) {
                memo.put(prefix, true);
                return true;
            }
        }
        memo.put(s,false);
        return false;
    }
}

---

✍ 부분 코드 설명

1. 변수 선언 & 초기화

class Solution {
     static int maxlen;
    public boolean wordBreak(String s, List<String> wordDict) {
      Map<String, Boolean> map = new HashMap<>();
        Set<String> wordSet = new HashSet<>(wordDict);
        maxlen=0;
        for(String word: wordDict) {
            maxlen = Math.max(maxlen, word.length());
        }

        return dfs(s, map, wordSet);
    }
    		...

• `map`: 탐색한 문자열과 그 결과 저장 
• `wordSet`: wordDict를 set 자료구조로 저장
• `maxLen`: wordDict 내 가장 긴 단어 길이 저장(불필요한 탐색 방지)

❓ Set으로 변경하여 탐색하는 이유
이후 dfs를 진행하면서 `contains()` 내장 함수를 사용할 예정
List와 Set 모두 해당 내장 함수를 제공하지만, 시간복잡도 면에서 차이가 남

`Set`은 평균적으로 O(1)의 시간복잡도를 갖지만, `List`는 O(N)의 시간복잡도로 Set이 더 효율적
그 이유는, Set은 해시 테이블을 기반으로 탐색을 진행하기에, 데이터를 찾을 때 해시값을 이용해 빠르게 찾음

반면에, List는 배열이나 연결리스트로 구현된다. 
따라서 각 요소를 순차적으로 비교하여 찾기 때문에 최악의 경우 모든 요소를 검사해야하므로 O(N)의 시간이 걸림

---

2. DFS 진행

class Solution {
    		...                    
     public static boolean dfs(String s, Map<String, Boolean> memo, Set<String> wordSet) {
        if(memo.containsKey(s)) return memo.get(s);
        if(wordSet.contains(s)) return true;

        for(int i=1;i<s.length();i++) {
            String prefix = s.substring(0,i);
            if(prefix.length()>maxlen){
                break;
            }
            if(wordSet.contains(prefix) && dfs(s.substring(i), memo, wordSet)) {
                memo.put(prefix, true);
                return true;
            }
        }
        memo.put(s,false);
        return false;
    }
}

 

1-1. 이미 탐색한 문자열인 경우 (`memo.conatinsKey`) 해당 문자열의 탐색 결과 반환

1-2. wordSet에 현재 문자열 `s`가 존재하는 경우 true 반환

2. 주어진 문자열 `s`의 처음부터 한 글자씩 늘려가면서 부분 문자열을 `prefix`에 저장

3. 만일, prefix의 길이가 max_len보다 긴 경우, 탐색하지않음

∵ 단어 사전에 있는 단어로만 문자열을 분해함
prefix 길이가 단어 사전 내 최장 길이의 단어보다 긴 경우, 탐색할 필요 없음 (어차피 단어 사전에 없음)

4. 단어 사전에 prefix가 존재하고 (분해 가능), 분할 이후 문자열 또한 존재하는 경우 return true

4번 로직이 재귀로 이루어지다 보니 어떻게 동작하는지 한 눈에 파악하기 어렵다.
아래에 그림을 통해 재귀 흐름을 설명하겠다.

dfs 문자열 분해

---

✨ 결과

왼쪽: maxLen을 사용한 경우 , 오른쪽: maxLen을 사용하지 않은 경우

 

아래는 DP를 활용해 푸는 방식이다.

dfs보다 효율적이나, dfs에서 maxLen을 사용한 경우와 비슷한 성능을 보였다.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean []dp = new boolean[s.length()+1];
        dp[0] = true;
        int max_len = 0;
        for(String word : wordDict) {
            max_len = Math.max(word.length(), max_len);
        }

        for(int i=1;i<=s.length();i++){
            for(int j =i-1;j>=Math.max(i-max_len-1, 0);j--){
                String check = s.substring(j,i);
                if(dp[j]&&wordDict.contains(check)){
                    dp[i] = true;
                    break;
                }
            }
        }
        System.out.println(dp[s.length()]);
        return dp[s.length()];
    }
}