Straightforward recursive solution

  • 4

    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


    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) {
            return res;
        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);
            		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.