320. Generalized Abbreviation

Q:

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

A:
就是一个个加上去。思路是类似于：DP吧？

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> list = new LinkedList<String>();
        list.add("");
        for(int i =0;i<word.length();i++){
            char ch = word.charAt(i);
            List<String> newList = new LinkedList<String>();
            for(String tmp : list){
                if(tmp.length() == 0){
                    newList.add(tmp+"1");
                }else{ //extract last number, NOTE: there might no digit at all
                    int val = 0;
                    int endIndex = tmp.length()-1;
                    while(endIndex >=0 && isDigit(tmp.charAt(endIndex))){
                        endIndex--;
                    }
                    if(endIndex!= tmp.length()-1){
                        val = Integer.parseInt(tmp.substring(endIndex+1));
                    }
                    newList.add(tmp.substring(0,endIndex+1)+ (val+1));
                }
                newList.add(tmp+ch);
            }
            list = newList;
        }
        return list;
    }
    private boolean isDigit(char ch){
        return ch>='0' && ch <= '9';
    }
}

Mistakes:
1:  word为空的时候，返回的List中，应该有一个""的字符串。   （这个有点儿自己定义的意思了）

******Recursive way ***********************

public class Solution {
    public List<String> generateAbbreviations(String word) {
        int n = word.length();
        List<String> list = new LinkedList();
        if( n ==0){
            list.add("");
            return list;
        }
        List<String> less = generateAbbreviations(word.substring(0,n-1));
        for(String str : less){
            list.add(str+word.charAt(n-1));
            int j = str.length()-1;// get the last in list, and do the addition
            while(j>=0 && Character.isDigit(str.charAt(j)))
                j--;
            int count = j == str.length()-1? 0:Integer.parseInt( str.substring(j+1));
            list.add(str.substring(0,j+1)+ (count +1) ) ;
        }
        return list;
    }
}