Redirecting to
NADOS

Abbreviation Using Backtracking

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a word.
2. You have to generate all abbrevations of that word.

Use recursion as suggested in question video
Input Format 
A string representing a word
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= length of string <= 32
Sample Input 
pep
Sample Output 
pep
pe1
p1p
p2
1ep
1e1
2p
3


  • Editorial

    We have to generate all the abbreviations of the string passed as an input.

    Example 1 -

    Input -

    pep

    Output -

    pep

    pe1

    p1p

    p2

    1ep

    1e1

    2p

    3

    Example 2  -

    Input -

    ac

    Output -

    ac

    a1

    1c

    2

    Example 3 -

    Input -

    a

    Output -

    a

    1

    Before proceeding towards the solution, we will first generate all the binaries of the length equal to length of input string.

    Let the input string be "pep".

    Binaries -

    000 -> pep

    001 -> pe1

    010 -> p1p

    011 -> p2

    100 -> 1ep

    101 -> 1e1

    110 -> 2p

    111 -> 3

    We can observe that whenever the bit is OFF, we will use the character of the string at that position and whenever the bit is ON, we will count all the ON bits  that are together and then replace them with the count of the ON bits.

    The number of abbreviations will be equal to 2n , where n = length of the string(as the number of binaries with given n is equal to 2n ).

    We can see that this question is like subsequence, we must maintain one more variable which will count the characters that were not included in the subsequence.

    Code: 

    public static void solution(String str, String asf,int count, int pos){
                                      if(pos == str.length()){
                                           if(count > 0){
                                               asf += count;
                                           }
                                           System.out.println(asf);
                                           return;
                                      }
                                      solution(str, asf + (count > 0 ? count : "" ) + str.charAt(pos), 0, pos + 1); //yes call -> including curr char
                                      solution(str, asf, count + 1, pos + 1); //not including curr char -> just converting letters to a number
                                }

    java false

    Code Explained -

    SIGNATURE of the function -

    public static void solution (String str, String asf,int count, int pos) {}

    str -Input string

    asf  - String that stores the answer till index pos at different levels.

    count  - store the count of characters that were not included in the subsequence just before the pos index.

    pos  - current index.

    We will make two calls at each level  -

    Call Yes  - Include the character at index pos in asf

    Call No -  Do not include the character at index pos in asf.

    When we make a NO CALL, we increase the pos variable and not include anything in the asf. We will also increase count variable as we are not including the current character in answer.

    When we make a YES CALL, we will check whether the count is more than zero. If the count is more than zero we will add the count and the character at pos index else we will just add the character at pos index. Also, we will make the count variable equal to zero. We are adding the count to the asf as we have to include the characters that we did not add earlier.

    We will make YES call before NO call because of the order of output.

    YES CALL -

    solution (str, asf + (count > 0 ? count : "" ) + str.charAt(pos), 0, pos + 1);

    NO CALL  -

    solution (str, asf, count + 1, pos + 1);

    The above explained method will be clearer by seeing the recursion diagram.

    In recursion diagram ,(a | b | c )  a refers to the test string , b refers to the asf and c refers to the count.

    Base case -

    We will return when pos will be equal to length of the string. Before returning we will print the asf. If the count will be greater than zero, we will append the count to the asf before printing it.

    Time Complexity  - O(2^N)

    Where N = length of the input string.

    As we are making two calls Yes / No at every index until our pos index is equal to the length of the string, therefore the complexity will be exponential and equal to 2 ^ N.

    Space Complexity  - O(N)

    Where N = length of the input string.

    We can observe that maximum depth of recursion tree any time is N. Therefore, the max space occupied at any time will be equal to the N. In the post order, the occupied space in recursion stack will be freed so the space occupied will not exceed N.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name