Java, LeetCode | 139. Word Break

🚀 풀이 후기

문제 이해도 어렵고, DP여서 풀이도 어려웠습니다.

List배열을 바로 Set으로 만드는 방법을 알게 됐습니다.

 List<String> wordDict = new ArrayList<>();
 Set<String> word = new HashSet<>(wordDict);

🌒 문제 설명

wordDict의 문자열들을 재조합했을 때 s를 완성시킬 수 있는지 검사하는 문제입니다.

Example 3에서는 wordDict의 단어들을 s를 이용해서 모두 만들 수는 있지만, wordDict를 재조합했을 때 s를 만들 수는 없어 false입니다.

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.

🌓 문제 풀이

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // wordDict 배열의 중복을 제거합니다.
        Set<String> word = new HashSet<>(wordDict);
        
        // dp 배열을 만듭니다.
        boolean[] dp = new boolean[s.length() + 1];
        
        // dp 배열의 0번 index는 s시작 전이기 때문에 무조건 true입니다.
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // j<= <i 까지 문자열을 쪼갭니다.
                String temp = s.substring(j, i);
                
                // dp배열에서 시작점이 true이고 temp가 word set 에 포함된 단어이면,
                if (dp[j] && word.contains(temp)) {
                    dp[i] = true; // temp 끝 인덱스 +1 인 곳에 true를 저장합니다.
                    break;
                }
            }
        }
        // dp 맨 끝 값을 반환합니다.
        return dp[s.length()];
    }
}

N: s의 길이

- 시간복잡도: O(N^3)

- 공간복잡도: O(N)

 

---

리트코드 문제

깃허브 코드