e.g. s = “catsandog”

wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

• Step 1: Visualize Examples
  • First Split Position
    • prefix “cat” ∈ wordDict
    • Check suffix “sandog”
      • “sand” ∈ wordDict
      • Remainder “og” is not breakable → fail
  • Second split position
    • prefix “cats” ∈ wordDict
    • Check suffix “andog”
      • “and” ∈ wordDict
      • Remainder “og” → fail

  In Step 1, we visualize the process as:

  • Try a prefix of the string.
  • If that prefix is in wordDict, recursively check if the suffix can also be segmented.

  This naturally suggests a prefix → suffix direction: we explore from the start of the string and work our way forward.

  This recursive visualization in Step 1 represents a top-down process: break the string into smaller suffixes and recursively solve them.

• Step 2: Find an Appropriate Subproblem

  In contrast, dynamic programming builds solutions bottom-up, by solving all smaller subproblems first and combining their results to solve larger ones.

  To enable this, we need to define subproblems in such a way that:

  • Each subproblem builds upon strictly smaller prefixes of the input.
  • We can iteratively compute the answer from dp[0] up to dp[n].

  We define the subproblem as:

  dp[i] = whether s[0..i-1] can be broken into words from wordDict
  

  That is, we evaluate whether the prefix up to index i is breakable, which seems to reverse the direction—focusing on prefixes, not suffixes.

  we create a structure that allows us to:

  • Start with the base case dp[0] = true (the empty string is trivially breakable).
  • Iterate from left to right.
  • For each i, check whether there exists a j < i such that dp[j] == true and s[j..i-1] ∈ wordDict.

  This reversal of direction isn’t a contradiction—it’s a deliberate transformation from a recursive formulation into an efficient iterative one. The recursive and DP solutions answer the same question, but the latter requires reframing the subproblem to enable bottom-up computation and memoization.

• Step 3: Find Relationships Among Subproblems

  For any position i (1 ≤ i ≤ n) we scan an earlier cut position j (0 ≤ j < i):

  • The left part s[0 .. j-1] is in the dictionary
  • The right part s[j .. i-1] is breakable

  If both hold for some j, then dp[i] = true otherwise it remains false.

• Step 4: Generalize the Relationship, i.e., find the State Transition Formula

\[dp[i] = ∨_{j=0}^{i-1} (dp[j] ∧ (s[j..i-1] ∈ wordDict))\]

• Step 5: Implement by Solving Subproblems in Order