Word Break
DFS + Memoization + HashSet

Goal simple hai: string ke har index par check karo ki kya wahan se dictionary ke kisi word se start karke end tak pahunch sakte ho. Agar same index dobara aaye, memo se cached answer le lo.

DFS = choices try karo

HashSet = word lookup fast

Memo = repeated work avoid

🧠 Core idea — Hinglish mein

Define karo dfs(i) = “kya s[i:] ko valid dictionary words mein tod sakte hain?”

Start at index i

Current suffix dekho.

Try every end j

Substring s[i:j] banao.

HashSet lookup

Agar word dict mein hai → dfs(j).

Memoize result

Same i dobara aaye toh direct answer.

Base case: agar i == len(s), matlab hum perfectly end tak segment kar chuke → True.

▶ Animated example

s = "applepenapple" wordDict = {"apple", "pen", "ape"}

Step 1 / 8

Press Play animation. Hum dfs(0) se start karenge.

currently checking dictionary word matched confirmed path

Call stack

dfs(0)

Memo cache

empty

🐍 Python solution

def wordBreak(s, wordDict):
    words = set(wordDict)
    memo = {}

    def dfs(i):
        # Reached the end successfully
        if i == len(s):
            return True

        # Same suffix already solved
        if i in memo:
            return memo[i]

        # Try every possible next word
        for j in range(i + 1, len(s) + 1):
            word = s[i:j]

            if word in words and dfs(j):
                memo[i] = True
                return True

        memo[i] = False
        return False

    return dfs(0)

Why memoization matters?

Without memoization, alag-alag word choices kabhi same index par wapas aa sakti hain. Fir wahi suffix baar-baar solve hota hai → exponential recursion ho sakti hai.

Memo ke saath har index ka answer max ek baar properly compute hota hai. Typical interview complexity ko roughly O(n²) states/substrings ke perspective se samjho, plus Python substring creation ka cost implementation-dependent hota hai.

Interview line: “I’ll use DFS to try valid dictionary prefixes, a HashSet for fast membership checks, and memoize by starting index so each suffix is solved once.”