139. Word Break

문제

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Solution

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);  // wordDict를 Set으로 만들어서 탐색 시간을 줄임
        int n = s.length();
        // dp[i]: 처음부터 i까지 분할 가능한지(wordDict에 존재하는지)
        boolean[] dp = new boolean[n];

        //dp 초기화
        for(int i=0;i<n;i++) {
            String sub = s.substring(0,i+1);
            if(wordSet.contains(sub)) {
                dp[i]=true;
            }
        }

        for(int i=0;i<n;i++) {
            if(dp[i]) {
                for(int j=i+1;j<n;j++) {
                    String sub = s.substring(i+1,j+1);
                    if(wordSet.contains(sub)) {
                        dp[j]=true;
                    }
                }
            }
        }

        return dp[n-1];
    }
}

회고

항상 DP 문제를 풀 때마다 dp[i] 정의에 어려움을 겪는다.

 

길이 n의 문자열 s에 대해, dp[i]는 s의 처음부터 i까지의 부분 문자열을 wordDict의 단어들로 분할할 수 있는지를 나타낸다.

 

문자열 s의 각 위치 i에 대해, dp[i]가 true일 때, i 이후의 위치 j까지의 부분 문자열이 wordDict에 존재하면 dp[j]를 true 설정한다. 이렇게 하면 s의 처음부터 끝까지의 각 부분 문자열이 wordDict의 단어들로 분할 가능한지 확인할 수 있다.

 

초기화를 단계에서

        for(int i=0;i<n;i++) {
            String sub = s.substring(0,i+1);
            if(wordSet.contains(sub)) {
                dp[i]=true;
            }
        }

s의 첫 인덱스부터 i 인덱스까지의 부분 문자열이 wordDict에 포함되는지 확인하는 작업을 수행했다. 이를 통해 문자열의 시작 구간이 wordDict의 단어들로 분리될 수 있는지를 설정하여, 이후 DP 연산의 기반을 마련했다.