Strings Pattern Hub

Levenshtein recurrence on rolling 1D row: if `w1[i] == w2[j]`, inherit `diag`; otherwise `1 + min(dp[j] /*delete*/, dp[j-1] /*insert*/, diag /*replace*/)`. Remember `dp[0] = i` on each row start.

Check `len(s1) + len(s2) == len(s3)` first. State `(i, j)` tracks whether `s1[:i]` and `s2[:j]` interleave to form `s3[:i + j]`. Rolling 1D row: `dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])`.

Rolling 1D DP tracking previous diagonal `diag`: if `text1[i] == text2[j]`, extend `diag + 1`; otherwise `max(dp[j], dp[j - 1])`. Space drops from `O(M * N)` to `O(min(M, N))`.

Expand outward from every odd (`(i, i)`) and even (`(i, i + 1)`) center in O(1) extra space, tracking `[bestStart, bestLen]` rather than allocating substrings on every expansion.

Define `dp[i] = True` iff prefix `s[:i]` can be segmented. Instead of checking every split `0..i`, probe each word `w` in `wordDict` backward from `i` (`dp[i - len(w)] and s[i-len(w):i] == w`) with a hash set or bounded lengths.