9 line easy JAVA solution


  • 39
    C
    public class Solution {
        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;
        }
    }

  • 1
    S

    This solution is awesome! How did you come up with this idea?


  • 0
    W

    Really nice and elegant recursion! However, there will be a lot of redundant recursive calls in this case. Using a cache for memorizing the list of abbreviations for sub cases could be faster.


  • 0
    L

    Would you mind telling me why my memorization code below doesn't speed up the program?

    public List<String> generateAbbreviations(String word) {
            HashMap<String, List<String>> abbr = new HashMap();
            return generateAbbreviations(word, abbr);
        }
        
        public List<String> generateAbbreviations(String word, HashMap<String, List<String>> abbr) {
            if(abbr.containsKey(word)) return abbr.get(word);
            List<String> ret = new ArrayList();
            int len = word.length();
            ret.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):"";
                    String ans = leftNum + word.substring(i, i+1) + right;
                    ret.add(ans);
                }
            }
            abbr.put(word, ret);
            return ret;
        }
    

  • 0
    J

    @liang54 The cache is never used.


  • 4
    P

    Here is the Memoized version of this method which significantly improves its runtime. I also realized that it is similar to String permutation problem.
    I don't know whether this kind of solution is acceptable in a real interview.

     public class Solution {
        Map<String, List<String>> map = new HashMap<>();
        public List<String> generateAbbreviations(String word) {
    	        List<String> res = new ArrayList<>();
    	        if(word.length() == 0 ) {
    	        	res.add("");
    	            return res;
    	        }
    	        if(map.containsKey(word))
    	            return map.get(word);
    	        res.add(String.valueOf(word.length()));    
    	        for(int i = 0; i < word.length(); i++) {
    	            String s = word.substring(i + 1);
    	            String left = i == 0 ? "" : "" + i;
    	            String ch = "" + word.charAt(i);
    	            for(String right : generateAbbreviations(s)) {
    	                res.add(left + ch + right);
    	            }
    	        }
    	        map.put(word, res);
    	        return res;
    	    }    
    }
    

  • 0

    Anyone please explains how this solution works?


  • 0
    Y
    This post is deleted!

  • 0

    @zhugejunwei

    a b c d e f
    1 b + recurse on rest
      2 c + recurse on rest
        3 d + recurse on rest
          4 e + recurse on rest 
            5 f + recurse on rest
    

    For the case of 1b + recurse(cdef), if recurse(cdef) returns "1d1f", then we just have to append "1b" to the head of that subsolution.

    Duplicate is removed obviously as you can see: no two iterations shares the same headings.

    Of course you also have to include solutions like "6" for "abcdef" but that can be handled as a trivial base case. Once that is handled, you can rest assured that there will be at least one letter in the other results. The loop iterate on this survivor letter's positin (i) and do the recursion as shown above.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.