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"] Show Company Tags Show Tags Show Similar Problems

Solution

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<String>();
        boolean keep[] = new boolean[word.length()];
        Arrays.fill(keep, true);
        for(int i = 0; i <= word.length(); i++) {
            findPattern(word, keep, i, 0, ans);
        }
        return ans;
    }

    public void findPattern(String word, boolean keep[], int remain, int minIdx, List<String> ans) {
        if(remain == 0) {
            ans.add(output(word, keep));
            return;
        }

        for(int i = minIdx; i < word.length(); i++) {
            keep[i] = false;
            findPattern(word, keep, remain-1, i+1, ans);
            keep[i] = true;
        }
    }

    public String output(String word, boolean keep[]) {
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < keep.length; i++) {
            if(keep[i]) {
                if(cnt != 0) sb.append(cnt);
                cnt = 0;
                sb.append(word.charAt(i));
            } else {
                cnt += 1;   
            }
        }
        if(cnt != 0) sb.append(cnt);
        return sb.toString();
    }
}