/*     * 320 Generalized Abbreviation      * 2016-7-6 by Mingyang      * 我一开始按照自己的方法去做，111a，这种只是每个位数上面替代成1，然后最后再把相连的数加起来     * 但是后面发现这个方法太麻烦了，参考了网上的解法：     * 对于每一个char，我们要么留着，要么变为数字，那位为了留着，我们加到现在的current里面，继续dfs     * 如果变数字，我们count++，当我们到最后的时候如果count！=0或者需要加char的时候     * 检查count是否为0，不为0就把数字粘上去，然后变为0     */    public static List
     
       generateAbbreviations(String word) {        List
      
        ret = new ArrayList
       
        ();        dfs1(ret, word, 0, "", 0);        return ret;    }    private static void dfs1(List
        
          ret, String word, int pos, String cur, int count) {        if (pos == word.length()) {            if (count > 0)                cur += count;            ret.add(cur);        } else {            dfs1(ret, word, pos + 1, cur, count + 1);            dfs1(ret, word, pos + 1, cur + (count > 0 ? count : "") + word.charAt(pos), 0);        }    }