LeetCode - 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".

제약사항

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

[전략]
DP 접근법을 이용
1. 각 단어를 HashMap으로 저장하고
2. 문자열 s를 0번째부터 j번째까지 잘라서 HashMap에 저장된 단어인지 확인

• 저장된 단어이면 0번째-j번째 자른 문자열에 대해 사전에 등록된 단어임을 기록 2차원 배열에 기록
• 저장되지 않은 단어이면 false 저장

3. 문자열 시작점(i)을 1씩 증가하며, 문자열 s의 0번째-i-1번째가 사전에 등록된 단어들로 구성되어 2차원 배열에 true로 기록된 경우에만 2번 과정을 반복

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int wordLen = s.length();
        Set<String> wordDictionary = new HashSet<String>();
        Boolean[][] wordDictSubset = new Boolean[wordLen][wordLen]; // false로 초기화

        for (String word : wordDict) {
            wordDictionary.add(word);
        }

        for (int i = 0; i < wordLen; i++) {
            boolean isPromise = false;
            if (i == 0 || wordDictSubset[0][i - 1]) {
                isPromise = true;
            }

            for (int j = i; j < wordLen; j++) {
                if (isPromise) {
                    if (wordDictionary.contains(s.substring(i, j + 1))) {
                        if (j == wordLen - 1) {
                            return true;
                        }
                        wordDictSubset[0][j] = true;

                    } else {
                        wordDictSubset[i][j] = false;
                    }
                }
            }
        }
        return false;
    }
}