LeetCode - Generalized Abbreviation

GeneralizedAbbreviation.java

// 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

// my solution 
public List<String> generateAbbreviations(String word) {
    List<String> res = new ArrayList<>();
    if(word == null) return res;
    double limit = Math.pow(2, word.length());
    long mask = 0;
    while(mask < limit){
        StringBuilder sb = new StringBuilder();
        int count = 0, submask  = 1;
        for(int i = 0; i < word.length(); i++){
            if((mask & submask) == 0){
                if(count > 0) {
                    sb.append(count);
                    count = 0;
                }
                sb.append(word.charAt(i));
            } else {
                count++;
            }
            submask <<= 1;
        }
        if(count > 0) sb.append(count);
        res.add(sb.toString());
        mask++;
    }
    return res;
}

// solution 2 
public List<String> generateAbbreviations(String word) {
    List<String> res = new ArrayList<String>();
    int len = word.length();
    res.add(len==0 ? "" : String.valueOf(len));
    for(int i = 0 ; i < len ; i++)
        for(String right : generateAbbreviations(word.substring(i+1))){
            String leftNum = i > 0 ? String.valueOf(i) : "";
            res.add( leftNum + word.substring(i, i + 1) + right );
        }
    return res;
}

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

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