320. Generalized Abbreviation

1.题意

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

例如result一开始为一个空list，这时候加[1],result 变成[[], [1]]. i变成2时候，对与result里边所有list 加2，因此result变成[[],[1],[2],[1,2]]

对于这个题，
可以首先变1位，然后加到list中["word", "1ord", "w1rd", "wo1d", "wor1"]

然后对于list里边已经变过1位的，再变1位，变的这位应该在原来那个数字后边，这样才能避免重复["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1"]，

按照这个方法对["2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1"]再变1位 ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1","2r1", "3d", "w3"]

最后对["2r1", "3d", "w3"]再变1位得到结果。

 public class Solution {  
   List<String> ans = new ArrayList<>();  
   public List<String> generateAbbreviations(String word) {  
     helper(word,0);   
     return ans;  
   }  
   public void helper(String word,int i){  
     ans.add(word);  
     for(; i <word.length(); i++){  
       if(!Character.isDigit(word.charAt(i))){  
         int[] ii = new int[1];  
         ii[0] = i;  
         helper(abbreviate(word,ii),ii[0]);  
       }  
     }  
   }  
   public String abbreviate(String s, int[] ii){  
     int i = ii[0];  
     int p1 = i-1;  
     while(p1 >=0 && Character.isDigit(s.charAt(p1)))  
       p1--;  
     int num = 0;  
     if(p1!=i-1)  
       num=Integer.valueOf(s.substring(p1+1,i));  
     num++;  
     ii[0]=p1+1;  
     return s.substring(0,p1+1)+ String.valueOf(num) + (i==s.length()?"":s.substring(i+1));  
   }  
 }  

方法二：
对于word的每一位，都可以abbreviate或者不abbreviate。结果长度：2^n

引用：https://discuss.leetcode.com/topic/32270/java-backtracking-solution

这种方法其实是在构造每个abbreviation，而不是从原有的word中修改获得abbreviation。

The idea is: for every character, we can keep it or abbreviate it. To keep it, we add it to the current solution and carry on backtracking. To abbreviate it, we omit it in the current solution, but increment the count, which indicates how many characters have we abbreviated. When we reach the end or need to put a character in the current solution, and count is bigger than zero, we add the number into the solution.

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