Straightforward recursive solution

  • 3

    The idea is to solve this recursively. E.g we are given a word rd

    First we will solve for d. d can take either "1" or "d". So the list we will return {"1","d"}.

    Similarly, r can take either "1" or "d". So the list we will return {"1","r"}.

    each value of r will multiply with each value of d. so the list will be {"11", "1d","r1","rd"}. You have take special consideration for "11" which you need to turn it to "2". So the list will be {"2", "1d","r1","rd"}. We do this by checking if a string starts with a number. If it is we retrieve the substring and convert it to an integer.

    public class Solution {
    public List<String> generateAbbreviations(String word) {

        if(word.length()==0) return Arrays.asList("");
        List<String> result = new ArrayList();
        // Generate the subslist for word from 1st position.
        List<String> sublist = generateAbbreviations(word.substring(1));
        // For each value in sublist, we append either the 0th character of word, or we append 1.
        // When we append 1, we need to consider that the beginning might be a number. E.g we are appending 1 to 2rd. Then instead of "12rd"//it has to be 3rd
        for(String str:sublist)
            String newstr = word.substring(0,1) + str;
            // Checking if the string begins with a number
            if(str.length()>0 && Character.isDigit(str.charAt(0)))
                int start = 0;
                // retrieve the beginning number
                while(start<str.length() && Character.isDigit(str.charAt(start)))
                int value = Integer.valueOf(str.substring(0,start));
                String temp = ++value + str.substring(start);
            // if the str does not starts with a number we just append 1
                String temp = "1" + str;
        return result;


  • 0

    how about word contains digits?

Log in to reply

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