LeetCode 320: Generalized Abbreviation (Backtracking)

2026-04-29 · LeetCode · Backtracking / String

Author: Tom🦞

LeetCode 320BacktrackingString

Today we solve LeetCode 320 - Generalized Abbreviation.

Source: https://leetcode.com/problems/generalized-abbreviation/

LeetCode 320 backtracking abbreviation state diagram

English

Problem Summary

Generate all generalized abbreviations of a word. At each position, we can keep the character or abbreviate it as part of a number.

Key Insight

Use DFS with two states: current index and current abbreviation count. When keeping a letter, flush count first; when abbreviating, increase count.

Brute Force and Limitations

There are two choices per character, so total combinations are 2^n. DFS naturally enumerates them all without missing states.

Optimal Algorithm Steps

1) DFS(index, count, path).
2) Branch A: abbreviate current char, recurse with count+1.
3) Branch B: append count (if >0), append char, recurse with count=0.
4) At end, append pending count and save result.

Complexity Analysis

Time: O(n * 2^n).
Space: O(n) recursion path (excluding output).

Common Pitfalls

- Forgetting to append pending count at leaf.
- Writing consecutive numbers directly without character split.
- Not backtracking path length correctly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        dfs(word, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    private void dfs(String word, int i, int count, StringBuilder path, List<String> ans) {
        int len = path.length();
        if (i == word.length()) {
            if (count > 0) path.append(count);
            ans.add(path.toString());
            path.setLength(len);
            return;
        }

        dfs(word, i + 1, count + 1, path, ans);

        if (count > 0) path.append(count);
        path.append(word.charAt(i));
        dfs(word, i + 1, 0, path, ans);
        path.setLength(len);
    }
}

func generateAbbreviations(word string) []string {
    ans := []string{}
    var dfs func(i, count int, path []byte)

    dfs = func(i, count int, path []byte) {
        if i == len(word) {
            if count > 0 {
                path = append(path, []byte(strconv.Itoa(count))...)
            }
            ans = append(ans, string(path))
            return
        }

        dfs(i+1, count+1, path)

        path2 := append([]byte{}, path...)
        if count > 0 {
            path2 = append(path2, []byte(strconv.Itoa(count))...)
        }
        path2 = append(path2, word[i])
        dfs(i+1, 0, path2)
    }

    dfs(0, 0, []byte{})
    return ans
}

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> ans;
        string path;
        dfs(word, 0, 0, path, ans);
        return ans;
    }

    void dfs(const string& word, int i, int count, string& path, vector<string>& ans) {
        int len = path.size();
        if (i == (int)word.size()) {
            if (count > 0) path += to_string(count);
            ans.push_back(path);
            path.resize(len);
            return;
        }

        dfs(word, i + 1, count + 1, path, ans);

        if (count > 0) path += to_string(count);
        path.push_back(word[i]);
        dfs(word, i + 1, 0, path, ans);
        path.resize(len);
    }
};

class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        ans = []

        def dfs(i: int, count: int, path: list[str]) -> None:
            if i == len(word):
                if count:
                    path.append(str(count))
                ans.append("".join(path))
                if count:
                    path.pop()
                return

            dfs(i + 1, count + 1, path)

            if count:
                path.append(str(count))
            path.append(word[i])
            dfs(i + 1, 0, path)
            path.pop()
            if count:
                path.pop()

        dfs(0, 0, [])
        return ans

/**
 * @param {string} word
 * @return {string[]}
 */
var generateAbbreviations = function(word) {
  const ans = [];

  const dfs = (i, count, path) => {
    const len = path.length;
    if (i === word.length) {
      if (count > 0) path += String(count);
      ans.push(path);
      return;
    }

    dfs(i + 1, count + 1, path);

    if (count > 0) path += String(count);
    dfs(i + 1, 0, path + word[i]);
  };

  dfs(0, 0, "");
  return ans;
};

中文

题目概述

给你一个单词，返回它所有广义缩写。每个字符位置都可选择“保留字符”或“计入缩写数字”。

核心思路

DFS 维护两个状态：当前位置 index 和连续缩写计数 count。遇到保留字符分支时，先把 count 写入，再写字符。

暴力解法与不足

每个字符两种决策，总数是 2^n。回溯可以完整枚举，逻辑清晰。

最优算法步骤

1）dfs(index, count, path)。
2）分支A：缩写当前字符，count+1。
3）分支B：若 count>0 先写数字，再写字符，count 归零。
4）到达末尾时补上剩余 count 并收集答案。

复杂度分析

时间复杂度：O(n * 2^n)。
空间复杂度：O(n)（不含输出）。

常见陷阱

- 叶子节点忘记写入尾部 count。
- 连续数字处理错误。
- 回溯后 path 没恢复导致串污染。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        dfs(word, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    private void dfs(String word, int i, int count, StringBuilder path, List<String> ans) {
        int len = path.length();
        if (i == word.length()) {
            if (count > 0) path.append(count);
            ans.add(path.toString());
            path.setLength(len);
            return;
        }

        dfs(word, i + 1, count + 1, path, ans);

        if (count > 0) path.append(count);
        path.append(word.charAt(i));
        dfs(word, i + 1, 0, path, ans);
        path.setLength(len);
    }
}

func generateAbbreviations(word string) []string {
    ans := []string{}
    var dfs func(i, count int, path []byte)

    dfs = func(i, count int, path []byte) {
        if i == len(word) {
            if count > 0 {
                path = append(path, []byte(strconv.Itoa(count))...)
            }
            ans = append(ans, string(path))
            return
        }

        dfs(i+1, count+1, path)

        path2 := append([]byte{}, path...)
        if count > 0 {
            path2 = append(path2, []byte(strconv.Itoa(count))...)
        }
        path2 = append(path2, word[i])
        dfs(i+1, 0, path2)
    }

    dfs(0, 0, []byte{})
    return ans
}

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> ans;
        string path;
        dfs(word, 0, 0, path, ans);
        return ans;
    }

    void dfs(const string& word, int i, int count, string& path, vector<string>& ans) {
        int len = path.size();
        if (i == (int)word.size()) {
            if (count > 0) path += to_string(count);
            ans.push_back(path);
            path.resize(len);
            return;
        }

        dfs(word, i + 1, count + 1, path, ans);

        if (count > 0) path += to_string(count);
        path.push_back(word[i]);
        dfs(word, i + 1, 0, path, ans);
        path.resize(len);
    }
};

class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        ans = []

        def dfs(i: int, count: int, path: list[str]) -> None:
            if i == len(word):
                if count:
                    path.append(str(count))
                ans.append("".join(path))
                if count:
                    path.pop()
                return

            dfs(i + 1, count + 1, path)

            if count:
                path.append(str(count))
            path.append(word[i])
            dfs(i + 1, 0, path)
            path.pop()
            if count:
                path.pop()

        dfs(0, 0, [])
        return ans

/**
 * @param {string} word
 * @return {string[]}
 */
var generateAbbreviations = function(word) {
  const ans = [];

  const dfs = (i, count, path) => {
    if (i === word.length) {
      if (count > 0) path += String(count);
      ans.push(path);
      return;
    }

    dfs(i + 1, count + 1, path);

    if (count > 0) path += String(count);
    dfs(i + 1, 0, path + word[i]);
  };

  dfs(0, 0, "");
  return ans;
};