[LeetCode] 139. Word Break -Java

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

Word Break - LeetCode

---

문제

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.

---

풀이

풀이 과정

문자열 s와 문자열들이 들어있는 리스트 wordDIct가 주어진다.
만약 문자열 s가 리스트에 있는 단어들로 분리될 수 있다면 true를 반환하고 그렇지 않으면 false를 return한다.

문자열 s의 처음부터 끝까지 순회하며 n번째 자리까지 리스트의 단어들로 만들 수 있는지 판단한다.
n번째 자리까지 true가 되는 조건은 두 가지를 만족해야한다.

1. n부터 앞으로 일정 길이만큼 잘라내었을 때 해당 단어가 리스트에 존재한다.
2. 잘라낸 단어 이전 까지의 결과가 true여야한다.

동적계획법을 이용하여 두 가지 조건을 탐색한다.

탐색 결과값을 저장할 배열을 선언하고 첫 번째 인덱스 값을 true로 설정한다.

// n번째 문자까지 탐색결과를 저장할 배열
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;

 

문자열 s의 각 자리를 순회하며 탐색한다.
각 자리에서 잘라낼 단어의 길이를 늘려가며 잘라낸 단어가 리스트에 존재하고 그 이전 결과값이 true인지 확인한다.
만약 조건을 만족한다면 현재 인덱스의 탐색값을 true로 저장하고 탐색을 종료한다.

// i번째 자리수가 참이되는 경우를 탐색
for(int i = 1; i <= s.length(); i++) {
    // 잘라낼 단어의 길이를 증가시키며 탐색
    for(int j = i - 1; j >= 0; j--) {
        String word = s.substring(j, i);
        // 잘라낸 단어가 리스트에 포함되고
        // 이전까지의 결과값이 true인 경우
        // 현재 인덱스의 결과를 true로 설정하고 탐색 종료
        if(wordDict.contains(word) && dp[j]) {
            dp[i] = true;
            break;
        }
    }
}

 

탐색이 완료되고 최종 결과값을 반환한다.

// 최종 탐색 결과값을 return
return dp[s.length()];

---

최종 코드

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // n번째 문자까지 탐색결과를 저장할 배열
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        // i번째 자리수가 참이되는 경우를 탐색
        for(int i = 1; i <= s.length(); i++) {
            // 잘라낼 단어의 길이를 증가시키며 탐색
            for(int j = i - 1; j >= 0; j--) {
                String word = s.substring(j, i);
                // 잘라낸 단어가 리스트에 포함되고
                // 이전까지의 결과값이 true인 경우
                // 현재 인덱스의 결과를 true로 설정하고 탐색 종료
                if(wordDict.contains(word) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        // 최종 탐색 결과값을 return
        return dp[s.length()];
    }
}

---