[LeetCode] 139. Word Break (Java)

leetcode.com/problems/word-break/

Word Break - LeetCode

 

## 접근방법

---

어떤 문자열이, 단어들의 조합으로 만들어졌는지 확인하는 문제다. 문자열을 재귀적으로 함수를 단순하게 호출한다면, 시간초과가 발생한다.

 

 

class Solution {
    HashSet<String> hs = new HashSet<>();
    
    public boolean isBreak(String s, int start, int end){
        if(hs.contains(s.substring(start, end)))
            return true;
        
        for(int i = start + 1; i < end; i++){
            if(isBreak(s, start, i) && isBreak(s, i, end))
                return true;
        }
        
        return false;
    }
    
    public boolean wordBreak(String s, List<String> wordDict){
        hs.add("");
        for(String str : wordDict) hs.add(str);
        
        return isBreak(s, 0, s.length());
    }
}

위의 코드가 시간초과가 발생하는 이유는, 같은 구간을 여러번 호출하고 있기 때문이다. 한번 확인된 구간에 대해서는 다시 확인하지 않도록, 메모이제이션을 사용하면 시간 복잡도를 줄일 수 있다.

 

 

하지만, 그것보다 DP를 사용해서 문제를 푸는 것이 훨씬 깔끔하고 좋다. 

DP[i] = 0 ~ i - 1의 부분 문자열이 단어들의 조합으로 만들어졌는지 여부(true, false)

 

 

DP[i]가 true가 되기 위해서는 다음 조건이 필요하다. i보다 작은 j에 대해서, "DP[j]가 true", "str.substring(j, i)이 wordDict에 포함" 두 조건이 만족되어야 true가 될 수 있다. DP의 개념에 의해서 i보다 작은 j는 모두 구해져 있다.

 

 

위의 DP개념을 바탕으로 코드를 작성하면 된다.

 

## 해설코드

---

 

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> hs = new HashSet<>();
        for(String str : wordDict) hs.add(str);
        
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        for(int i = 1; i <= s.length(); i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j] && hs.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}