320. Generalized Abbreviation

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

A word’s generalized abbreviation can be constructed by taking any number of non-overlapping substrings and replacing them with their respective lengths. For example, “abcde” can be abbreviated into “a3e” (“bcd” turned into “3”), “1bcd1” (“a” and “e” both turned into “1”), and “23” (“ab” turned into “2” and “cde” turned into “3”).

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

Example 1:

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

Example 2:

Input: word = "a"
Output: ["1","a"]

Code

class Solution {
    private void helper(String word, String curr, List<String> res, int start, int count) {
        if (start == word.length()) {
            if (count != 0){
                curr += count;
            }

            res.add(curr);
            return;
        }

        helper(word, curr + (count == 0 ? "" : count) + word.charAt(start), res, start + 1, 0);
        helper(word, curr, res, start + 1, count + 1);
    }
    
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        helper(word, "", res, 0, 0);
        return res;
    }
}