Valid Word Abbreviation Leetcode solution using JAVA language

 Valid word abbreviation problem will be solved by using 2 pointer approach, it has certain limitations:

- abbreviation must not contain leading zeros 

  - example: 

word: laughing out loud

abbr: l07outl 

explanation: because of 0 before 7 it's not valid abbreviation, why? due to the start of the digits in abbr with zero, which is called leading zero.

- adjacent substrings in the abbreviation is not accepted

  - example: 

word: as soon as possible

abbr: a42e

explanation: soon and as are adjaced substring, and abbreviation of soon and as is 42 collectively, which is not allowed.

- replacing an empty substring is not allowed

  - example:

word: abbreviation

abbr: a0bbreviation

explanation: zero between a and b is a replacement of empty substring which is not allowed


Solution approach:


- we will take two pointers (i and j), and i will be pointing to the start of the "word" and j will be pointing to the start of the "abbreviation"

- iterate the while loop until i < word.length() and j < abbr.length()

- inside the loop the first if condition will check weather the current character of the abbreaviation is digit:

  - if it is digit then iterate another while loop to get the numbers we have in the abbreviation for example if we have abbr is like i11n, to get this 11 out of the abbr we have this while loop unitl j < abbr.length() and the jth character is a digit

  - once we have the number we will iterate i by that number for example i = i + 11 (for above case).

  - now the else part, if the current character is not the digit then we have another conditional statement that will check:

    - if the current character of the word i.e. word.charAt(i)

    - and current character of the abbr i.e. abbr.charAt(j)

    - does not matches then it will return false

- iterate i and j

- if the both pointers reaches to the the end of there respective strings i.e i for word and j for abbr return true, else return false



Solution:

class Solution {

    public boolean validWordAbbreviation(String word, String abbr) {

int i=0, j=0;

        int wL = word.length(), aL = abbr.length();

        while(i < wL && j < aL){

            if(Character.isDigit(abbr.charAt(j))){

                if(abbr.charAt(j) == '0'){

                    return false;

                }

                

                int num = 0;

                while(j<aL && Character.isDigit(abbr.charAt(j))){

                    num = num * 10 + (abbr.charAt(j) - '0');

                    j++;

                }

                i = i + num;

            }else {

                if(word.charAt(i) != abbr.charAt(j)){

                    return false;

                }

                i++;

                j++;

            }

        }

        

        return i == wL && j == aL;

    }

}



explanation of num = num * 10 + (abbr.charAt(j) - '0');

- above line is used to get the complete number from the abbreviation

- (abbr.charAt(j) - '0') is used to convert character to the number

- num * 10 will shift the number to the left


let me explain with example word = internationalorganization abbr = i23s


initially num = 0

now by referencing above program j is pointing to abbr, now when j will be at 1 index it will the character '2' so num  will be

-j=1

num = 0 * 10 + ('2' - '0')

('2' - '0') = 2 (in the integer, not in the character)

0 * 10 = 0

nums  = 0 + 2 = 2


-j=2

nums = 2 * 10 + ('3' - '0')

('3' - '0') = 3 (in the integer, not in the character)

2 * 10 = 20 (shifting 2 to the left so other characters can add up to become a complete number)

nums = 20 + 3 = 23



If you have any doubts please leave the comment




Comments

Post a Comment

Popular posts from this blog

Anomalies in Database

Anomaly is a fault which occurs in the poorly designed database , which leads to inconsistent, redundant and inefficient data. There are three kind of anomalies: - Insertion anomaly - Updation anomaly - Deletion anomaly Insertion Anomaly It occurs when we want to insert a particular kind of data, let's say Data#1, but due to the absence of a certain data, let's say Data#2, we were unable to add. Example If we have only one table for saving student and course, named std_course. We won't be able to add the new course until, we have the student information. std_course Table  Student_ID Student_Name Course Instructor Instructor_Contact 101 Ali DBMS Mr. Khan 123456789 102 Ahmed OS Mr. Ahsan 987654321 Suppos...
Read more

Kubernetes terms made easy

when we have docker compose and we can define rules to run our containerized applications over there ... so why do we need k8s...? Well we can certainly manage very small containers... but handling large scale applications through this will certainly be a nightmare... Because ... large apps will need to scale automatically.. and docker compose requires manual intervention and scripting .. ahhh who will re invent the wheel... Let's k8s do this... Now when we know the importance of k8s .. we have to learn it's core components and it's architecture level working... k8$ environment have a company named ... control pane .. who is responsible for managing and running kubernetes clusters ....  This company, named control pane.. have a CEO.. named, API Server ...I wasn't talking about the actual CEO of kubernetes 😅... just an analogy... Every one discuss there matters with API server ... and api server talks to everyone ... It's kind of a brain of the company...  Next come...
Read more