Straightforward recursive solution


  • 3
    S

    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;
            result.add(newstr);
    
            // 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)))
                {
                    start++;
                }
    
                int value = Integer.valueOf(str.substring(0,start));
    
                String temp = ++value + str.substring(start);
                result.add(temp);
            }
            
            // if the str does not starts with a number we just append 1
            else
            {
                String temp = "1" + str;
                result.add(temp);
            }
    
        }
    
        return result;
    
    }
    

    }


  • 0
    Y

    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.