Formatted question description: https://leetcode.ca/all/408.html

408. Valid Word Abbreviation (Easy)

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

Companies:
Facebook

Related Topics:
String

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/valid-word-abbreviation/

// Time: O(M+N)
// Space: O(1)
class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0, M = word.size(), N = abbr.size();
        while (i < M && j < N) {
            if (isalpha(abbr[j])) {
                if (word[i] != abbr[j]) return false;
                ++i;
                ++j;
                continue;
            }
            int len = 0;
            while (j < N && isdigit(abbr[j])) {
                len = 10 * len + (abbr[j++] - '0');
                if (!len) return false;
            }
            i += len;
        }
        return i == M && j == N;
    }
};

Java

  • class Solution {
        public boolean validWordAbbreviation(String word, String abbr) {
            List<String> abbrList = new ArrayList<String>();
            StringBuffer sb = new StringBuffer();
            int abbrLength = abbr.length();
            for (int i = 0; i < abbrLength; i++) {
                char c = abbr.charAt(i);
                if (c >= 'A') {
                    if (sb.length() > 0) {
                        abbrList.add(sb.toString());
                        sb = new StringBuffer();
                    }
                    abbrList.add(String.valueOf(c));
                } else
                    sb.append(c);
            }
            if (sb.length() > 0)
                abbrList.add(sb.toString());
            int wordLength = word.length();
            int abbrListLength = abbrList.size();
            int wordIndex = 0;
            int abbrIndex = 0;
            while (wordIndex < wordLength && abbrIndex < abbrListLength) {
                String curAbbr = abbrList.get(abbrIndex);
                if (curAbbr.charAt(0) >= 'A') {
                    char abbrChar = curAbbr.charAt(0);
                    char c = word.charAt(wordIndex);
                    if (abbrChar != c)
                        return false;
                    else {
                        wordIndex++;
                        abbrIndex++;
                    }
                } else {
                    if (curAbbr.charAt(0) == '0')
                        return false;
                    int skip = Integer.parseInt(curAbbr);
                    wordIndex += skip;
                    abbrIndex++;
                }
            }
            return wordIndex == wordLength && abbrIndex == abbrListLength;
        }
    }
    
  • // OJ: https://leetcode.com/problems/valid-word-abbreviation/
    // Time: O(M+N)
    // Space: O(1)
    class Solution {
    public:
        bool validWordAbbreviation(string word, string abbr) {
            int i = 0, j = 0, M = word.size(), N = abbr.size();
            while (i < M && j < N) {
                if (isalpha(abbr[j])) {
                    if (word[i] != abbr[j]) return false;
                    ++i;
                    ++j;
                    continue;
                }
                int len = 0;
                while (j < N && isdigit(abbr[j])) {
                    len = 10 * len + (abbr[j++] - '0');
                    if (!len) return false;
                }
                i += len;
            }
            return i == M && j == N;
        }
    };
    
  • class Solution(object):
      def validWordAbbreviation(self, dest, src):
        """
        :type word: str
        :type abbr: str
        :rtype: bool
        """
        start = j = 0
        digit = False
        for i in range(0, len(src)):
          if src[i].isdigit():
            if not digit:
              if src[i] == "0":
                return False
              start = i
              digit = True
          else:
            if digit:
              jump = int(src[start:i])
              digit = False
              j += jump
            if j >= len(dest) or src[i] != dest[j]:
              return False
            j += 1
          if i == len(src) - 1:
            if digit:
              jump = int(src[start:i + 1])
              digit = False
              j += jump
              if j != len(dest):
                return False
        return True
    
    

All Problems

All Solutions