Two easy straight forward methods in JAVA with exp: backtracking, Divide & Conquer


  • 9
    S

    Backtracking:

    public class Solution {
            public List<String> generateAbbreviations(String word) {
                List<String> res = new ArrayList<String>();
                helper(word, 0, "", res, false);
                return res;
            }
            // isAbbrPrev: false, we can add alphabet or abbreviation(number) next round
            // isAbbrPrev: true,  we can add alphabet ONLY next round
            public void helper(String word, int start, String cur, List<String> res, boolean isAbbrPrev) {
                if (start == word.length()) {
                    res.add(cur);
                    return;
                }
                if (isAbbrPrev == false) { // we can add abbreviation (num)
                    for(int end=start+1; end<=word.length(); end++) { // iterate all abbreviations from 'start'
                        helper(word, end, cur + Integer.toString(end-start), res, true);
                    }
                }
                helper(word, start+1, cur + word.charAt(start), res, false); // adding one word each time
            }
        }
    

    D & C:

    public class Solution {
        public List<String> generateAbbreviations(String word) {
            Set<String> s = helper(word);
            List<String> res = new ArrayList<String>(s);
            return res;
        }
    
        public Set<String> helper(String word) {
            int length = word.length();
            Set<String> res = new HashSet<String>();
            if (length == 0) {
                res.add("");
                return res;
            }
            res.add(Integer.toString(length));
            for(int i=0; i<length; i++) {    // we separate String into two parts with word.charAt(i)
                Set<String> left = helper(word.substring(0,i));
                Set<String> right = helper(word.substring(i+1, length));
                for(String strLeft : left) {
                    for(String strRight : right) {
                        res.add(strLeft + word.charAt(i) + strRight);
                    }
                }
            }
            return res;
        }
    }

  • 0
    E

    Your D&C solution seems to have LTE problem for test case "segmentation". One way to possibly shorten the time is to use subfix only instead of both prefix and subfix. See my code here: https://leetcode.com/discuss/76010/straightforward-recursive-solution


  • 0
    D

    Why is your divide&conquer method correct? for "word", does your method support "4" abbreviation case? Thanks :)


  • 0

    D&C is easy-understanding but caused TLE :(


  • 1
    P

    Here is a different version of fast Divide and Conquer based solution :

    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 str : generateAbbreviations(s)) {
    	                res.add(left + ch + str);
    	            }
    	        }
    	        map.put(word, res);
    	        return res;
    	    }
               
    }
    

Log in to reply
 

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