Today I Learned

오늘은 지방 내려갔다가 올라와서 피곤하지만 코테를 풀었다.

Word Break

139. Word Break https://leetcode.com/problems/word-break/description/

문제

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.

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.

풀이 과정

• 이 문제는 DP, 동적 프로그래밍을 활용해 문제를 풀었다.

1. 동적 프로그래밍(DP) 사용
   DP를 사용하여 문자열의 각 위치까지의 나누어진 단어가 단어 사전에 있는지 여부를 저장한다.
   이를 위해 DP 배열을 선언해둔다.

2. 부분 문제 정의
   dp[i]를 문자열의 처음부터 i까지의 부분 문자열이 단어 사전에 있는 단어들로 나누어질 수 있는지 여부를 나타내는 boolean 값으로 정의한다.

3. 점화식 세우기
   dp[i] = true일 조건: j가 0부터 i-1까지 변화할 때, dp[j]가 true이고, s.substring(j, i)가 단어 사전에 있는 단어인 경우
   위의 조건 중 하나라도 만족하는 경우 dp[i]를 true로 설정한다.

4. 문자열의 첫 번째 문자부터 시작하기 때문에, dp[0]은 항상 true다.

5. 문자열의 각 위치마다 dp 배열을 업데이트하면서, 문자열 전체가 단어 사전에 있는 단어들로 나누어질 수 있는지 여부를 확인한다.

6. 마지막으로, 문자열 전체가 단어 사전에 있는 단어들로 나누어질 수 있는지 여부인 dp[s.length()] 값을 반환한다!

Java 코드

import java.util.*;

public class M03_wordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
      
      Set<String> wordSet = new HashSet<>(wordDict);

      
      boolean[] dp = new boolean[s.length() + 1];
      dp[0] = true;

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

      return dp[s.length()];
    }
}