golang 解法, 执行用时: 32 ms, 内存消耗: 7 MB, 提交时间: 2023-10-17 20:15:52

func generateAbbreviations(word string) []string {
	n := len(word)

	res := []string{}
	var dfs func(i, k int, path string)
	dfs = func(i, k int, path string) {
		if i == n {
			if k != 0 {  // 如果计数不为0, 则转为 字符串,加到末尾.
				path += strconv.Itoa(k)
			}
			res = append(res, path)
			return
		}
		if k == 0 {  // 计数为0, 则 不用转数字, 直接加 当前 字符.
			dfs(i+1, 0, path+string(word[i]))
		} else {  // 不为0, 先加 计数, 再加 字符
			dfs(i+1, 0, path+strconv.Itoa(k)+string(word[i]))
		}  // 不加字符, 计数++
		dfs(i+1, k+1, path)
	}

	dfs(0, 0, "")
	return res
}

// 二进制
func generateAbbreviations2(word string) (ans []string) {
    n := len(word)
    for i := 0; i < (1<<n); i++ {
        s := []byte{}
        cnt := 0
        for j := n - 1; j >= 0; j-- {
            if i >> j & 1 == 1 {
                if cnt > 0 {
                    s = append(s, strconv.Itoa(cnt)...)
                }
                s = append(s, word[n-1-j])
                cnt = 0
            } else {
                cnt++
            }
        }
        if cnt > 0 {
            s = append(s, strconv.Itoa(cnt)...)
        }
        ans = append(ans, string(s))
    }
    return    
}

python3 解法, 执行用时: 160 ms, 内存消耗: 19.2 MB, 提交时间: 2023-10-17 20:14:54

class Solution:
    def generateAbbreviations1(self, word: str) -> List[str]:
        res = []
        
        def helper(i, tmp, cnt):
            """
            cnt 代表前面已经记录多少数字了
            """
            if i == len(word):
                if cnt > 0: tmp += str(cnt)
                res.append(tmp)
            else:
                helper(i + 1, tmp, cnt + 1)
                helper(i + 1, tmp + (str(cnt) if cnt > 0 else "") + word[i], 0)
            
        helper(0, "", 0)
        return res

    # 回溯2
    def generateAbbreviations2(self, word: str) -> List[str]:       
        res = []
        n = len(word)
        
        def helper(i, tmp):
            if i == n:
                res.append(tmp)
            else:
                for j in range(i, n):
                    num = str(j - i) if j - i > 0 else ""
                    helper(j + 1, tmp + num + word[j])
                helper(n, tmp + str(n - i))
        
        helper(0, "")
        return res
        
    # 位运算
    def generateAbbreviations(self, word: str) -> List[str]:
        n = len(word)
        res = []
        for i in range(2 ** n):
            tmp = ""
            # 记录1的个数
            one_cnt = 0
            for w, f in zip(word, bin(i)[2:].rjust(n, "0")):
                if f == "0":
                    if one_cnt > 0:
                        tmp += str(one_cnt)
                        one_cnt = 0
                    tmp += w
                else:
                    one_cnt += 1
            if one_cnt > 0:
                tmp += str(one_cnt)
            res.append(tmp)
        return res

cpp 解法, 执行用时: 28 ms, 内存消耗: 14.3 MB, 提交时间: 2023-10-17 20:13:32

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        int n = word.size(), mask = 0, end = 1 << n;
        vector<string> res(1 << n);
        while (mask < end) {
            int i = 0;
            while (i < n) {
                if ((mask & (1 << i)) == 0) {  // 不进行替换
                    res[mask].push_back(word[i++]);
                } else {  // 使用数字替换
                    int j = i;
                    while (mask & (1 << j)) j++;
                    res[mask].append(to_string(j - i));
                    i = j;
                }
            }
            ++mask;
        }        
        return res;
    }

};

// dfs 回溯
class Solution1 {
    vector<string> res;
    string word;
    int n;
public:
    void dfs(int start, int cnt, string path) {
        if (start == n) {
            if (cnt) path.append(to_string(cnt));
            res.push_back(path);
            return;
        }
        dfs(start + 1, cnt + 1, path);  // 进行替换

        if (cnt) path.append(to_string(cnt));
        path.push_back(word[start]);
        dfs(start + 1, 0, path);    // 不进行替换
    }
    vector<string> generateAbbreviations(string word) {
        this -> word = word;
        this -> n = word.size();
        dfs(0, 0, "");
        return res;
    }
};

java 解法, 执行用时: 17 ms, 内存消耗: 47.7 MB, 提交时间: 2023-10-17 20:12:20

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        for (int x = 0; x < (1 << word.length()); ++x) // loop through all possible x
            ans.add(abbr(word, x));
        return ans;
    }

    // build the abbreviation for word from number x
    private String abbr(String word, int x) {
        StringBuilder builder = new StringBuilder();
        int k = 0, n = word.length(); // k is the count of consecutive ones in x
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) { // bit is zero, we keep word.charAt(i)
                if (k != 0) { // we have abbreviated k characters
                    builder.append(k);
                    k = 0; // reset the counter k
                }
                builder.append(word.charAt(i));
            }
            else // bit is one, increase k
                ++k;
        }
        if (k != 0) builder.append(k); //don't forget to append the last k if non zero
        return builder.toString();
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 46.1 MB, 提交时间: 2023-10-17 20:12:09

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

    // i is the current position
    // k is the count of consecutive abbreviated characters
    private void backtrack(List<String> ans, StringBuilder builder, String word, int i, int k){
        int len = builder.length(); // keep the length of builder
        if(i == word.length()){
            if (k != 0) builder.append(k); // append the last k if non zero
            ans.add(builder.toString());
        } else {
            // the branch that word.charAt(i) is abbreviated
            backtrack(ans, builder, word, i + 1, k + 1);

            // the branch that word.charAt(i) is kept
            if (k != 0) builder.append(k);
            builder.append(word.charAt(i));
            backtrack(ans, builder, word, i + 1, 0);
        }
        builder.setLength(len); // reset builder to the original state
    }
}