Java Two Pointer Solution


  • 0
    J

    Use two pointers to traverse the two strings at the same time. Each time we see a number in abbr (say the value of the number is num), we move pointer of word forward by num steps. Then check if the two characters pointed by the two pointers are the same.

    Corner case:

    1. If the number starts with '0', it's invalid.
    2. If the last character in abbr is a number and both pointers point at the end of the strings, return true.
    public class Solution {
        public boolean validWordAbbreviation(String word, String abbr) {
            if (word == null && abbr == null) return true;
            if (word == null || abbr == null) return false;
            
            int len1 = word.length();
            int len2 = abbr.length();
            int i = 0;
            int j = 0;
            while (i < len1 && j < len2) {
                int num = 0;
                while (j < len2 && Character.isDigit(abbr.charAt(j))) {
                    int digit = abbr.charAt(j++) - '0';
                    num = num * 10 + digit;
                    if (num == 0) return false;     // a number starts with 0
                }
                i += num;
                if (i < len1 && j < len2 && word.charAt(i) != abbr.charAt(j))
                    return false;
                if (i == len1 && j == len2) return true;    // i and j reach the end at the same time
                i++;
                j++;
            }
            
            return i == len1 && j == len2;
        }
    }
    

  • 0
    L

    It is a clean code. Especially, iterating over to read the number before comparing the character makes it short and succinct. Good work!

    @jwang137 said in Java Two Pointer Solution:

    Corner case:

    If the number starts with '0', it's invalid.
    If the last character in abbr is a number and both pointers point at the end of the strings, return true.

    public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
    if (word == null && abbr == null) return true;
    if (word == null || abbr == null) return false;

        int len1 = word.length();
        int len2 = abbr.length();
        int i = 0;
        int j = 0;
        while (i < len1 && j < len2) {
            int num = 0;
            while (j < len2 && Character.isDigit(abbr.charAt(j))) {
                int digit = abbr.charAt(j++) - '0';
                num = num * 10 + digit;
                if (num == 0) return false;     // a number starts with 0
            }
            i += num;
            if (i < len1 && j < len2 && word.charAt(i) != abbr.charAt(j))
                return false;
            if (i == len1 && j == len2) return true;    // i and j reach the end at the same time
            i++;
            j++;
        }
        
        return i == len1 && j == len2;
    }
    

    }


Log in to reply
 

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