Word Break

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

Word Break - LeetCode

 

주어진 문자열을 주어진 사전 안의 있는 단어로 분해할 수 있는지 물어보는 문제이다.
최초 문제 풀이시 DFS로 시도하였으나 시간 초과가 발생하였다. DP 카테고리의 문제이므로 DP로 풀어볼 아이디어를 찾았다.

 

주어진 문자열을 한글자씩 늘려 i번재 글자 까지가 분해할 수 있는지 확인해 가는 방식으로 했다. dp[i]를 특정 위치에서 양쪽으로 나눈다면 왼쪽과 오른쪽이 모두 분해 가능할 때 dp[i] 또한 분해 가능하다고 할 수 있다.
따라서 dp[i]에서의 값을 확인하기 위해서 i 까지의 각 위치 j를 기준으로 하여 왼쪽 구간이 분해 가능한지 기존 dp배열에서 확인한 후 뒷 구간은 사전 내에서 찾아보았다. 글자 수를 늘리면서 dp배열을 확인해 왔기 때문에 0번 인덱스에서 j 번 인덱스까지는 확인되고 저장되어 있기 때문에 빠른 속도로 체크가 가능하다. 아래는 최종적으로 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
  
    public boolean wordBreak(String s, List<String> wordDict) {  
        boolean[] dp = new boolean[s.length() + 1];  
        dp[0] = true;  
  
        for(int i = 0; i < dp.length; i++){  
            for(int j = 0; j <= i; j++){  
                if(dp[j] == true){  
                    String check = s.substring(j, i);  
                    if(wordDict.contains(check)){  
                        dp[i] = true;  
                        break;  
                    }  
                }  
            }  
        }  
  
        return dp[s.length()];  
    }  
  
}