LeetCode Word Break JAVA 풀이

https://leetcode.com/problems/word-break/

문제

s 를 스페이스(공백)으로 나누었을 때 나눠진 부분 단어들이 wordDict 리스트에 포함되어있다면 true, 아니라면 false 리턴

제한사항

풀이

감이 전혀 안와서 블로그를 통해 답을 확인했다.

DP를 이용해서 풀면 된다.

 

boolean dp 를 s.length + 1 만큼 선언해준다.

dp 배열의 값들은 해당 index 로 단어를 끊었을 때 wordDict 에 포함되면 True 처리를 한다.

 

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        // dp[0] 은 아무것도 나뉘어지지 않은 상태를 의미, 뒷부분을 잘라서 확인할 때 사용되므로 true 처리
        dp[0] = true; 
        
        for(int i = 1; i <= len; i ++) { // substring 을 이용하므로 i는 0번 idx 부터 탐색을 의미
            for(int j = i - 1; j >= 0; j --) { // i-1 자리부터 탐색
                String word = s.substring(j, i); // j ~ i-1 까지 단어 분리
                
                // 분리한 단어가 Dict 에 포함 + dp[j] 앞전 단어가 Dict에 포함
                if(wordDict.contains(word) && dp[j]) { 
                    dp[i] = true; // i번째에 true 처리 함으로써 어딘가~i-1까지 Dict에 포함되었음을 표시
                    break; // 앞부분까지 더 확인하지 않아도 되니 j에 대한 for문 탈출
                }
            }
        }

        return dp[len]; //마지막 idx에 대해서 값 return == 마지막 분리 단어까지 Dict 에 포함되었는지
    }
}

 

처음에 봤을 때는 이해가 잘 되지 않았는데 손코딩을 통해서 깨닫게 되었다.

i 는 계속 오른쪽으로 순차 탐색하고, j는 i 번째 단어로 끝나는 분리 단어에 대해서 wordDict 에 포함되는지 보면 된다.

 

예시를 leetcode 로 들어보자.

s = "leetcode", wordDict = ["leet", "code"], s.length = 8

 

따라서 처음 dp는 아래와 같이 된다.

dp = [T, F, F, F, F, F, F, F, F]

 

1) i = 1, j = i - 1 = 0, word = s.substring(0, 1) = "l" -> wordDict 포함 X

2) i = 2, j = 2 - 1 = 1, word = s.substring(1, 2) = "e" -> wordDict 포함 X

  2-1) i = 2, j = 1 - 1 = 0, word = s.substring(0, 2) = "le" -> 포함 X

3) i = 3, j = 3 - 1 = 2, word = substring(2, 3) = "e" -> 포함 X

  3-1) i = 3, j = 2 - 1 = 1, word = substring(1, 3) = "ee" -> 포함 X

  3-2) i = 3, j = 0, word = "lee" -> 포함 X

4) i = 4, j = 3, word = "t" -> 포함 X

...

   4-3) i = 4, j = 0, word = "leet" -> 포함 O + dp[0] = true => 따라서 dp[4] = true, 4개까지 포함시켜서 끊으면 Dict 에 포함된다는 뜻이 된다.  dp = [T, F, F, F, T, F, F, F, F]

... ...

   8-3) i = 8, j = 4, word = "code" -> 포함 O + dp[4] = true => dp[8] = true,  dp = [T, F, F, F, T, F, F, F, T]

 

for문이 완료 되었으니 dp[8] 을 return 하면 된다.

 

substring의 j ~ i - 1 과 dp[len+1] 를 잘 이해하면 될 거같다.

참고

 

https://hyojun.tistory.com/entry/LeetCode-139-Word-Break-Java