Generalized Abbreviation

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

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Thoughts

刚开始想依次遍历每个字符, 然后左右分治的做, 但题目要求是简写的要合并成一个数字, 左右分治没有合并. 实际上可以依然遍历, 但不是左右分治, 而是分别对简写该字母和不简写该字母做讨论.

Code

class Solution {
    private void dfs(String word, int pos, String cur, int count, List<String> res) {
        if (pos == word.length()) {
            if (count > 0) {
                cur += count;
            }
            res.add(cur);
        } else {
            dfs(word, pos + 1, cur, count + 1, res);
            dfs(word, pos + 1, cur + (count > 0 ? count : "") + word.charAt(pos), 0, res);
        }
    }

    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        dfs(word, 0, "", 0, res);
        return res;
    }
}

Analysis

每个字符可以简写和不简写两种, 一共O(2^N), N为string长度.