320. Generalized Abbreviation

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"]

Solution:

Method 1: DFS

We use DFS to search for all valid outputs.

When we go through the word and check every character, in any character, we can do two things:

1. Abbreviate this character.

2. Do not abbreviate this character.

In the first case, we just pass the current states to the next recursion.

In the second, case, we need to add the previously abbreviated count to the current path, with the current character, and pass it to the next recursion.



Code:

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        helper(word, result, "", 0, 0);
        return result;
    }
    public void helper(String word, List<String> result, String path, int count, int pos) {
        if (pos == word.length()) {
            if (count > 0) {
                path += count;
            }
            result.add(path);
            return;
        }
        else {
            // abbreviate this character
            helper(word, result, path, count + 1, pos + 1);
            
            // do not abbreviate this character
            helper(word, result, path + (count > 0 ? count : "") + word.charAt(pos), 0, pos + 1);
        }
    }
}

Method 2: Bit Manipulation (Iterative)

We can use the binary representation of two to the power of the number's length, to have a mapping with each character in the word.

Let's see an example of "word":

0000 word
0001 wor1
0010 wo1d
0011 wo2
0100 w1rd
0101 w1r1
0110 w2d
0111 w3
1000 1ord
1001 1or1
1010 1o1d
1011 1o2
1100 2rd
1101 2r1
1110 3d
1111 4

Notice that when we have a 1, the corresponding character is abbreviated.

When we have a 0, we keep this character.



Code:

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, word.length()); i++) {
            int count = 0;
            String abbr = "";
            for (int j = 0; j < word.length(); j++) {
                if (((i >> j) & 1) == 1) {
                    count++;
                }
                else {
                    if (count != 0) {
                        abbr += count;
                        count = 0;
                    }
                    abbr += word.charAt(j);
                }
            }
            if (count != 0) {
                abbr += count;
            }
            result.add(abbr);
        }
        return result;
    }
}