Straightforward recursive solution


  • 4
    E

    The idea is kind of straightforward: for a given string, think of all possible first substrings that are converted to an integer. For example, for

    word
    

    we have the following possibilities:

    w --> 1 (rem: ord)
    wo --> 2 (rem: rd)
    wor --> 3 (rem: d)
    word --> 4 (rem: null)
    

    For each case, the remainder (subfix) is going through exactly the same procedure as word, which is obviously a recursion.

    Code in Java:

    public class Solution {
    public List<String> generateAbbreviations(String word) {
        int L = word.length();
        return generate(word, 0, L-1);
    }
    
    private List<String> generate(String str, int left, int right) {
        List<String> res = new ArrayList<>();
        if(left>right) {
            res.add("");
            return res;
        }
        res.add(str.substring(left,right+1));
        for(int start=left; start<=right; start++) { // i: the location where the first number starts
            String strLeft = str.substring(left, start);
            for(int end=start; end<=right; end++) {
            	if(end!=right) {
    	            List<String> listRight = generate(str, end+2, right);
    	            for(String s : listRight)
    	                res.add(strLeft + (end-start+1) + str.substring(end+1, end+2) + s);
            	}
            	else
            		res.add(strLeft + (end-start+1));
            }
        }
        return res;
    }
    }

Log in to reply
 

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