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"]
/**
This question allows us to partially abbreviate a word. The shorthand rule is that several letters can be represented by numbers, but there can be no two adjacent numbers. For details, please refer to the example given in the title. According to my previous experience, This list of all the circumstances must be written with DFS, but I will not think of recursion for a while, then I counted the number of all the cases given in the title, is 16, and word There are 4 letters, just 2 to the 4th power. Is this coincidence? Of course not. Later I found out that if I write 0 to 15 binary, each one can correspond to one case, as shown below:

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

Then we can observe the law, where the 0 is the original letter, the single 1 or 1, if it is a number of 1 together, it is required to count the number, replace the corresponding letter with this number Since the law is found out, the code is well written, as shown below:
*/
import java.util.*;

public class GeneralizedAbbreviation {
    public static List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<String>();
        backtrack(result, word, 0, "", 0);
        return result;
    }
   
    static void backtrack(List result, String word, int position, String current, int count) {
        if(position == word.length()) {
            if(count > 0) {
                current += count; 
            }
            result.add(current);
        } else {
//use digit instead of this character
            backtrack(result, word, position + 1, current, count + 1);
//use this character itself
            backtrack(result, word, position + 1, current + (count > 0 ? count : "") + word.charAt(position), 0);
        }
    }

public static void main(String args[]){
String word = "word";
List<String> words = generateAbbreviations(word);
System.out.println(Arrays.toString(words.toArray()));
}
}

No comments:

Post a Comment