Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

String Recursion
DSA

String Recursion

Learn recursive approaches for processing, generating, and transforming strings.

Recognition Cheat Sheet

If you see…Think…
Split a string into partsString Partition Recursion
All valid partitionsTry every split
Palindrome partitionsSplit + palindrome check
Restore IP addressesSplit + length/range check
Word BreakSplit + dictionary check

Main Trigger

“Split the string into valid parts” → String Partition Recursion

The Basic Idea

At every position, try every possible ending for the current substring.

Palindrome partitioning of “aab” — non-palindrome prefixes kill their own branches:

Palindrome Partitioning

Cut a string into all combinations of palindromic pieces.

At each position try every prefix; keep it only if it is a palindrome, then recurse on the remainder. Non-palindrome prefixes die immediately, pruning the exponential tree. The valid partitions that reach the end are the answers.

TREE VISUALIZER
Steps –
"aab"take"a"→"ab"take"ab"✗take"a"→"b"take"b"✓take"aa"→"b"
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        partition(start, path):
                      
                        2
                          if start == len(s): output path
                      
                        3
                          for end in start+1 .. len(s):
                      
                        4
                            prefix = s[start:end]
                      
                        5
                            if isPalindrome(prefix):
                      
                        6
                              partition(end, path + [prefix])
                      
"abc"

Take "a"
  ↓
solve "bc"

Take "ab"
  ↓
solve "c"

Take "abc"
  ↓
solve ""

The pattern is:

Choose end
   ↓
Take substring
   ↓
Check if valid
   ↓
Recurse on remaining string
   ↓
Undo choice

1. Generic String Partition

Java Template

public void partition(
        String s,
        int start,
        List<String> path,
        List<List<String>> res) {

    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int end = start; end < s.length(); end++) {

        String part =
            s.substring(start, end + 1);

        if (!isValid(part))
            continue;

        path.add(part);

        partition(
            s,
            end + 1,
            path,
            res
        );

        path.remove(path.size() - 1);
    }
}
def partition(s, start, path, res):
    if start == len(s):
        res.append(path[:])
        return

    for end in range(start, len(s)):

        part = s[start:end + 1]

        if not is_valid(part):
            continue

        path.append(part)

        partition(s, end + 1, path, res)

        path.pop()
void partition(string& s, int start,
               vector<string>& path, vector<vector<string>>& res) {
    if (start == (int)s.size()) {
        res.push_back(path);
        return;
    }

    for (int end = start; end < (int)s.size(); end++) {
        string part = s.substr(start, end - start + 1);

        if (!isValid(part))
            continue;

        path.push_back(part);

        partition(s, end + 1, path, res);

        path.pop_back();
    }
}
function partition(s, start, path, res) {
  if (start === s.length) {
    res.push([...path]);
    return;
  }

  for (let end = start; end < s.length; end++) {
    const part = s.substring(start, end + 1);

    if (!isValid(part))
      continue;

    path.push(part);

    partition(s, end + 1, path, res);

    path.pop();
  }
}

Recognition

String + try every split + validate each part → String Partition Recursion

2. Palindrome Partitioning

Split the string so every part is a palindrome.

Example:

"aab"

Possible:

["a", "a", "b"]
["aa", "b"]

Java

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();

    backtrack(
        s,
        0,
        new ArrayList<>(),
        res
    );

    return res;
}

private void backtrack(
        String s,
        int start,
        List<String> path,
        List<List<String>> res) {

    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int end = start; end < s.length(); end++) {

        if (!isPalindrome(s, start, end))
            continue;

        path.add(
            s.substring(start, end + 1)
        );

        backtrack(
            s,
            end + 1,
            path,
            res
        );

        path.remove(path.size() - 1);
    }
}

private boolean isPalindrome(
        String s,
        int left,
        int right) {

    while (left < right) {

        if (s.charAt(left) != s.charAt(right))
            return false;

        left++;
        right--;
    }

    return true;
}
def partition(s):
    res = []

    def backtrack(start, path):
        if start == len(s):
            res.append(path[:])
            return

        for end in range(start, len(s)):

            if not is_palindrome(s, start, end):
                continue

            path.append(s[start:end + 1])

            backtrack(end + 1, path)

            path.pop()

    backtrack(0, [])
    return res

def is_palindrome(s, left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    backtrack(s, 0, {}, res);
    return res;
}

void backtrack(string& s, int start,
               vector<string> path, vector<vector<string>>& res) {
    if (start == (int)s.size()) {
        res.push_back(path);
        return;
    }

    for (int end = start; end < (int)s.size(); end++) {

        if (!isPalindrome(s, start, end))
            continue;

        path.push_back(s.substr(start, end - start + 1));

        backtrack(s, end + 1, path, res);

        path.pop_back();
    }
}

bool isPalindrome(string& s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}
function partition(s) {
  const res = [];

  function backtrack(start, path) {
    if (start === s.length) {
      res.push([...path]);
      return;
    }

    for (let end = start; end < s.length; end++) {
      if (!isPalindrome(s, start, end))
        continue;

      path.push(s.substring(start, end + 1));

      backtrack(end + 1, path);

      path.pop();
    }
  }

  backtrack(0, []);
  return res;
}

function isPalindrome(s, left, right) {
  while (left < right) {
    if (s[left] !== s[right])
      return false;
    left++;
    right--;
  }
  return true;
}

Recognition

All palindrome partitions → Try every split + check palindrome

3. Restore IP Addresses

An IP address contains exactly 4 parts.

Each part:

1–3 digits
0–255
No leading zero unless the part is "0"

Java

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<>();

    backtrack(
        s,
        0,
        0,
        new StringBuilder(),
        res
    );

    return res;
}

private void backtrack(
        String s,
        int start,
        int parts,
        StringBuilder path,
        List<String> res) {

    if (parts == 4) {

        if (start == s.length())
            res.add(path.substring(0, path.length() - 1));

        return;
    }

    for (int end = start;
         end < Math.min(s.length(), start + 3);
         end++) {

        String part =
            s.substring(start, end + 1);

        if (!isValidPart(part))
            continue;

        int oldLength = path.length();

        path.append(part).append('.');

        backtrack(
            s,
            end + 1,
            parts + 1,
            path,
            res
        );

        path.setLength(oldLength);
    }
}

private boolean isValidPart(String part) {

    if (part.length() > 1 &&
        part.charAt(0) == '0')
        return false;

    int value = Integer.parseInt(part);

    return value <= 255;
}
def restore_ip_addresses(s):
    res = []

    def backtrack(start, parts, path):
        if parts == 4:
            if start == len(s):
                res.append(path[:-1])
            return

        for end in range(start, min(len(s), start + 3)):
            part = s[start:end + 1]

            if not is_valid_part(part):
                continue

            old_length = len(path)

            path += part + '.'

            backtrack(end + 1, parts + 1, path)

            del path[old_length:]

    backtrack(0, 0, "")
    return res

def is_valid_part(part):
    if len(part) > 1 and part[0] == '0':
        return False
    return int(part) <= 255
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    string path;
    backtrack(s, 0, 0, path, res);
    return res;
}

void backtrack(string& s, int start, int parts,
               string& path, vector<string>& res) {
    if (parts == 4) {
        if (start == (int)s.size())
            res.push_back(path.substr(0, path.size() - 1));
        return;
    }

    for (int end = start;
         end < min((int)s.size(), start + 3);
         end++) {
        string part = s.substr(start, end - start + 1);

        if (!isValidPart(part))
            continue;

        int oldLength = path.size();

        path += part + '.';

        backtrack(s, end + 1, parts + 1, path, res);

        path.resize(oldLength);
    }
}

bool isValidPart(string& part) {
    if (part.size() > 1 && part[0] == '0')
        return false;
    return stoi(part) <= 255;
}
function restoreIpAddresses(s) {
  const res = [];

  function backtrack(start, parts, path) {
    if (parts === 4) {
      if (start === s.length)
        res.push(path.slice(0, -1));
      return;
    }

    for (let end = start;
         end < Math.min(s.length, start + 3);
         end++) {
      const part = s.substring(start, end + 1);

      if (!isValidPart(part))
        continue;

      const oldLength = path.length;

      path += part + '.';

      backtrack(end + 1, parts + 1, path);

      path = path.slice(0, oldLength);
    }
  }

  backtrack(0, 0, "");
  return res;
}

function isValidPart(part) {
  if (part.length > 1 && part[0] === '0')
    return false;
  return parseInt(part) <= 255;
}

Recognition

Restore IP → Split into exactly 4 valid parts

4. Word Break

Try splitting the string into words that exist in a dictionary.

Example:

s = "leetcode"

dict = ["leet", "code"]

→ "leet" + "code"

Java

public boolean wordBreak(
        String s,
        List<String> wordDict) {

    Set<String> dict =
        new HashSet<>(wordDict);

    return backtrack(s, 0, dict);
}

private boolean backtrack(
        String s,
        int start,
        Set<String> dict) {

    if (start == s.length())
        return true;

    for (int end = start + 1;
         end <= s.length();
         end++) {

        String word =
            s.substring(start, end);

        if (!dict.contains(word))
            continue;

        if (backtrack(s, end, dict))
            return true;
    }

    return false;
}
def word_break(s, word_dict):
    dict_set = set(word_dict)
    return backtrack(s, 0, dict_set)

def backtrack(s, start, dict_set):
    if start == len(s):
        return True

    for end in range(start + 1, len(s) + 1):
        word = s[start:end]

        if word not in dict_set:
            continue

        if backtrack(s, end, dict_set):
            return True

    return False
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    return backtrack(s, 0, dict);
}

bool backtrack(string& s, int start, unordered_set<string>& dict) {
    if (start == (int)s.size())
        return true;

    for (int end = start + 1; end <= (int)s.size(); end++) {
        string word = s.substr(start, end - start);

        if (!dict.count(word))
            continue;

        if (backtrack(s, end, dict))
            return true;
    }

    return false;
}
function wordBreak(s, wordDict) {
  const dict = new Set(wordDict);
  return backtrack(s, 0, dict);
}

function backtrack(s, start, dict) {
  if (start === s.length)
    return true;

  for (let end = start + 1; end <= s.length; end++) {
    const word = s.substring(start, end);

    if (!dict.has(word))
      continue;

    if (backtrack(s, end, dict))
      return true;
  }

  return false;
}

Recognition

Can the string be split into dictionary words? → Try every prefix + dictionary lookup

5. Word Break with Memoization

Plain recursion can solve the same suffix repeatedly.

Use memoization to avoid that.

Java

public boolean wordBreak(
        String s,
        List<String> wordDict) {

    Set<String> dict =
        new HashSet<>(wordDict);

    Boolean[] memo =
        new Boolean[s.length()];

    return backtrack(
        s,
        0,
        dict,
        memo
    );
}

private boolean backtrack(
        String s,
        int start,
        Set<String> dict,
        Boolean[] memo) {

    if (start == s.length())
        return true;

    if (memo[start] != null)
        return memo[start];

    for (int end = start + 1;
         end <= s.length();
         end++) {

        String word =
            s.substring(start, end);

        if (dict.contains(word) &&
            backtrack(s, end, dict, memo)) {

            return memo[start] = true;
        }
    }

    return memo[start] = false;
}
def word_break(s, word_dict):
    dict_set = set(word_dict)
    memo = [None] * len(s)
    return backtrack(s, 0, dict_set, memo)

def backtrack(s, start, dict_set, memo):
    if start == len(s):
        return True

    if memo[start] is not None:
        return memo[start]

    for end in range(start + 1, len(s) + 1):
        word = s[start:end]

        if word in dict_set and backtrack(s, end, dict_set, memo):
            memo[start] = True
            return True

    memo[start] = False
    return False
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<int> memo(s.size(), -1);
    return backtrack(s, 0, dict, memo);
}

bool backtrack(string& s, int start,
               unordered_set<string>& dict, vector<int>& memo) {
    if (start == (int)s.size())
        return true;

    if (memo[start] != -1)
        return memo[start];

    for (int end = start + 1; end <= (int)s.size(); end++) {
        string word = s.substr(start, end - start);

        if (dict.count(word) && backtrack(s, end, dict, memo)) {
            return memo[start] = true;
        }
    }

    return memo[start] = false;
}
function wordBreak(s, wordDict) {
  const dict = new Set(wordDict);
  const memo = new Array(s.length).fill(null);
  return backtrack(s, 0, dict, memo);
}

function backtrack(s, start, dict, memo) {
  if (start === s.length)
    return true;

  if (memo[start] !== null)
    return memo[start];

  for (let end = start + 1; end <= s.length; end++) {
    const word = s.substring(start, end);

    if (dict.has(word) && backtrack(s, end, dict, memo)) {
      return (memo[start] = true);
    }
  }

  return (memo[start] = false);
}

Recognition

String partition + repeated suffix states → Memoization / DP

String Partition Pattern Evolution

Try every split
    ↓
Validate substring
    ↓
Palindrome check
    ↓
Range / length check
    ↓
Dictionary lookup
    ↓
Memoization when states repeat

Common Mistakes

1. Recursing with the wrong index

After choosing:

s.substring(start, end + 1)

continue from:

end + 1

Not:

start + 1

2. Forgetting to undo

After recursion:

path.remove(path.size() - 1);

Every choice must be undone before trying the next split.

3. Accepting invalid substrings

Always validate before recursing:

if (!isValid(part))
    continue;

4. Missing memoization

If the same start position is reached repeatedly:

start = 5
start = 5
start = 5

cache the result.

Pattern Summary

Split string into parts
→ String Partition Recursion

Palindrome parts
→ Split + palindrome check

Valid IP
→ Split + 4 parts + range check

Dictionary words
→ Split + HashSet lookup

Repeated suffix states
→ Memoization / DP

Quick Rule

Choose an ending → validate the substring → recurse from the next position → undo.

My Private Notes

Notes are auto-saved locally to this device.