Word Break

Word Break

leetcode 139번 문제.

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

Word Break - LeetCode

 

 

 

 

1. 문제

 

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.

 

주어진 문자열 's'를 wordDict의 문자로 나눌 수 있으면 true를, 나눌 수 없다면 false를 반환

 

 

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.

 

 

 

 

2. 풀이

■ 풀이 방법

이 문제는 주어진 문자열 's'를 재귀적으로 나누어서 풀 수 있다.

예를 들어 다음과 같은 예를 생각해보자.

 

s = "catsdog",  wordDict = {"cat", "cats", "dog"}

 

이때 "catsdog"를 앞에서부터 나눠 본다고 하면 ["cat" + "sdog"]와 ["cats" + "dog"] 두 가지 경우가 나온다. 

이제 wordDict에 의해 나뉜 부분 문자열을 봐보자.

우선 "sdog"는 wordDict에 의해 나누어질 수 없다.

하지만 "dog"는 wordDict에 의해 나뉘어 질 수 있다.

따라서 "catsdog"는 "cats" + "dog"로 나뉘어 질 수 있다.

 

dp["catsdog"] 를 "catsdog"를 주어진 wordDict로 나눌 수 있는지 여부를 뜻한다고 하자.

그렇다면 앞의 예에서 다음과 같은 점화식이 성립한다.

 

dp["catsdog"] = ANY(dp["sdog"], dp["dog"])

 

즉 "catsdog"가 wordDict에 의해 나뉘는지 여부는 "catsdog"를 앞에서부터 wordDict로 나누었을 때 남겨진 부분 문자열들 중 단 하나라도 wordDict로 나누어질 수 있는지에 달려있다.

 

이를 일반화하면 다음과 같은 점화식이 성립한다.

 

dp[Stirng] = ANY(dp[subString1], dp[subString2], ....)

 

위의 점화식에 따라 각 dp[subString]을 계산하고 저장하는 dp 방식으로 문제를 해결한다.

 

예를 들어 "catsdog"의 경우 int[7]의 배열을 만들고 dp["g"], dp["og"], dp["dog"] .. 순으로 값을 저장한다.

 

 

 

■ code

□ wordBreak

dp() 메서드를 통해 memorization을 채우고 문제의 답을 저장한 memorization[s.length()]를 반환한다.

 

[wordBreak]

int[] memorization;   //[1]

public boolean wordBreak(String s, List<String> wordDict) {
        memorization = new int[s.length() + 1];
        dp(s, wordDict);
        return memorization[s.length()] == 2;
}

● [1] : dp[subString]을 저장하는 배열. 0은 비어있는 상태, 1은 나눌 수 없는 경우, 2는 나눌 수 있는 경우를 뜻한다.

 

 

□ dp

점화식을 통해 재귀적으로 memorization을 채우는 메서드

 

[dp]

public int dp(String subWord, List<String> wordDict) {
        if (memorization[subWord.length()] != 0) {
            return memorization[subWord.length()];
        }

        String tempWord = "";
        for (int i = 0; i < subWord.length(); i++) {
            tempWord += subWord.charAt(i);
            if (wordDict.contains(tempWord)) {
                if (subWord.length() == tempWord.length()) {
                    memorization[subWord.length()] = 2;
                    return memorization[subWord.length()];
                }
                if (dp(subWord.substring(i + 1), wordDict) == 2) {
                    memorization[subWord.length()] = 2;
                    return memorization[subWord.length()];
                }
            }
        }
        memorization[subWord.length()] = 1;
        return memorization[subWord.length()];
}

● [1] : memorization에 저장된 값이 있으면 그 값을 바로 반환한다.

● [2] : 주어진 문자의 앞에서부터 한 문자씩 추가하여 wordDict로 나눌 수 있는지를 확인한다.

● [3] : 만약 주어진 문자열 subWord와 한 문자씩 추가되는 tempWord가 같다면 주어진 subWord 자체를 wordDict로 나눌 수 있으며

            로 바로 memorization에 2 값을 삽입한다.

● [4] : tempWord에 의해 나뉜 subString을 dp에 넣어 재귀적으로 dp[subString]의 값을 구한다.

             반복문 중 단 하나라도 dp[subString] = 2인 경우 subWord도 나뉘어질 수 있기 때문에 memorization에 2값을 삽입한다.

● [5] : dp[subString] 중 어떤 것도 나누어지지 않는 경우 memorization에 1을 삽입하고 반환한다.

 

 

 

■ 전체 코드

[전체 코드]

import java.util.List;

public class Solution {

    int[] memorization;

    public int dp(String subWord, List<String> wordDict) {
        if (memorization[subWord.length()] != 0) {
            return memorization[subWord.length()];
        }

        String tempWord = "";
        for (int i = 0; i < subWord.length(); i++) {
            tempWord += subWord.charAt(i);
            if (wordDict.contains(tempWord)) {
                if (subWord.length() == tempWord.length()) {
                    memorization[subWord.length()] = 2;
                    return memorization[subWord.length()];
                }
                if (dp(subWord.substring(i + 1), wordDict) == 2) {
                    memorization[subWord.length()] = 2;
                    return memorization[subWord.length()];
                }
            }
        }
        memorization[subWord.length()] = 1;
        return memorization[subWord.length()];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        memorization = new int[s.length() + 1];
        dp(s, wordDict);
        return memorization[s.length()] == 2;
    }
}