[LeetCode] 139. Word Break 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Word Break

---

문제 요약 (Word Break)

문자열 s와 단어 사전 wordDict가 주어졌을 때, s를 사전의 단어들로 나눌 수 있는지 판별하는 문제.

• 문제 링크: https://leetcode.com/problems/word-break

---

🤔 처음 떠올린 아이디어

처음에는 단순하게 "백트래킹"을 생각했지만,   이느 중복으로 많은 부분 문자열을 검사하게 되어 비효율적이다.
그래서 자연스럽게 이렇게 질문했다.

“부분 문자열을 이미 검사한 결과를 저장하면 반복 계산을 줄일 수 있지 않을까?”

즉, 당연하게 DP 를 이용해야겠다고 떠올렸다.

---

💡 방법1: 재귀 + 메모이제이션 (Top-Down)

그럼 이제 DP 배열이 가지는 의미를 명확히 정의해야 한다.

재귀의 경우 인덱스의 뒤에서부터 알고리즘이 진행되기 때문에 DP[idx] 의 의미를
각 위치 idx에서 idx부터 끝까지 나눌 수 있는지 여부 로 정의해야 한다.

배열 의미 정의

• dp[idx] = true → 문자열 s[idx:](idx부터 끝까지)를 단어 사전으로 나눌 수 있음
• dp[idx] = false → 나눌 수 없음

---

🧠 부분 문제 정의와 DP 배열

1. 문제를 작은 부분 문제로 쪼갠다

• 전체 문자열이 아니라 s[idx:] 기준으로 생각
• 기준 인덱스 idx에 대해 “idx부터 끝까지 나눌 수 있는가?”라는 질문으로 배열 의미를 정의

2. Base case를 먼저 정한다

• idx == s.length() → 끝까지 성공했으므로 true

3. 점화식을 배열 의미에 맞춰 작성

dp[idx] = exists end ∈ [idx+1, s.length] such that
             s[idx:end] ∈ wordDict AND dp[end] == true

---

🔹 Top-Down 재귀 + DP 코드 (Java)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Boolean[] memo = new Boolean[s.length()];
        return solve(s, wordSet, 0, memo);
    }

    private boolean solve(String s, Set<String> wordSet, int idx, Boolean[] memo) {
        if(idx == s.length()) return true;
        if(memo[idx] != null) return memo[idx];

        for(int end = idx + 1; end <= s.length(); end++) {
            String sub = s.substring(idx, end);
            if(wordSet.contains(sub) && solve(s, wordSet, end, memo)) {
                memo[idx] = true;
                return true;
            }
        }

        memo[idx] = false;
        return false;
    }
}

---

🔹 Bottom-Up DP로 바꾸기

for 문은 인덱스 앞부터 검사하므로,
재귀로 이해한 논리를 0부터 i까지 나눌 수 있는지로 변환하여 생각한다.

• dp[i] = true → s[0:i]까지 단어 사전으로 나눌 수 있음

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 빈 문자열은 항상 나눌 수 있음

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

        return dp[n];
    }
}

📈 시간/공간 복잡도

• 시간: 모든 idx와 end 확인 → O(n²)
• 공간: DP 배열 + Set → O(n + k), k = 단어 사전 크기

---

📌 예제

s = "leetcode"
wordDict = ["leet", "code"]

문자열 길이: 8

• 목표: "leet" + "code"로 나눌 수 있는가?

1️⃣ Top-Down 재귀 + 메모이제이션

DP 배열: memo[idx] = idx부터 끝까지 나눌 수 있는가

idx = 0: "leet" in wordDict? → yes → solve(4)
idx = 4: "code" in wordDict? → yes → solve(8)
idx = 8: 끝 → true

memo 상태 변화:
memo[0] = true
memo[4] = true
memo[8] = true (끝)

• 재귀 호출 순서

solve(0)
└─ solve(4)
     └─ solve(8)

• 배열 의미: “idx부터 끝까지 나눌 수 있음 여부”
• 이미 계산한 idx는 바로 재사용 가능 → 중복 호출 방지

2️⃣ Bottom-Up 반복문 DP

DP 배열: dp[i] = 0부터 i까지 나눌 수 있는가

i = 1~8
dp[0] = true

i=4: check dp[0] && s[0:4]="leet" in wordDict → true
dp[4] = true

i=8: check dp[4] && s[4:8]="code" in wordDict → true
dp[8] = true

• 배열 의미: “처음부터 여기까지 나눌 수 있음
• 점차 작은 문제부터 쌓아서 전체 문자열까지 계산

dp 배열 변화:
dp[0] = T
dp[1] = F
dp[2] = F
dp[3] = F
dp[4] = T
dp[5] = F
dp[6] = F
dp[7] = F
dp[8] = T

---

📝 이번 문제에서 얻은 깨달음

• DP 배열 정의가 핵심 → “부분 문제 기준”을 명확히 잡아야 한다.
• 재귀로 문제 정의 → Bottom-Up으로 최적화가 직관적 학습 순서.
• Word Break는 부분 문자열 검사 + 메모이제이션의 대표 예제이며, 배열 의미를 한 번 정하면 재귀든 반복문이든 쉽게 변환 가능하다.