2Brute2Best
🔥0
05

String partitioning (Backtracking Sub-pattern)

Cut off a valid first piece of the string, then recurse on the rest; a full cut of the string is one answer.

Signals in the problem statement
  • ›

    "partition s so that every substring is a palindrome"

  • ›

    "all valid IP addresses" from a digit string

  • ›

    "all sentences" made of dictionary words

What makes it different

Palindrome Partitioning checks each piece; a precomputed isPal table makes the check O(1). Restore IP Addresses has exactly 4 pieces of length 1–3, no leading zeros, value ≤ 255, and prunes on the length left. Word Break II reaches the same suffix many times, so it memoizes the sentences for each start index.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Palindrome Partitioning
    Basic Anchor·LeetCode #131
    Medium
  2. 2
    Restore IP Addresses
    Basic Reinforcement·LeetCode #93
    Medium
  3. 3
    Word Break II
    Slight Variation·LeetCode #140
    Hard

Template

partition-template.cpp
// String partitioning: cut off a valid first piece s[start..end], recurse on the rest.
// Here the rule is "piece is a palindrome", answered in O(1) by a table built once in O(n^2).
void build(const string& s, int start, const vector<vector<bool>>& ok,
           vector<string>& pieces, vector<vector<string>>& out) {
    if (start == (int)s.size()) { out.push_back(pieces); return; } // the whole string is cut
    for (int end = start; end < (int)s.size(); end++) {
        if (!ok[start][end]) continue;                   // invalid piece: prune this branch
        pieces.push_back(s.substr(start, end - start + 1));
        build(s, end + 1, ok, pieces, out);
        pieces.pop_back();
    }
}

vector<vector<string>> partition(const string& s) {
    int n = s.size();
    vector<vector<bool>> ok(n, vector<bool>(n, false));  // ok[i][j]: s[i..j] is a palindrome
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            ok[i][j] = s[i] == s[j] && (j - i < 2 || ok[i + 1][j - 1]);
    vector<vector<string>> out;
    vector<string> pieces;
    build(s, 0, ok, pieces, out);
    return out;
}
Remember this · Backtracking
Trigger
"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.
Think
At each step, what are my choices, and how do I undo a choice?
Key question
What is my state, when is it complete, and when do I prune?
Combination sumConstraint satisfaction