##### Welcome to Subscribe On Youtube

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.

• 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;
}
}

############

class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
int m = word.length(), n = abbr.length();
int i = 0, j = 0;
while (i < m) {
if (j >= n) {
return false;
}
if (word.charAt(i) == abbr.charAt(j)) {
++i;
++j;
continue;
}
int k = j;
while (k < n && Character.isDigit(abbr.charAt(k))) {
++k;
}
String t = abbr.substring(j, k);
if (j == k || t.charAt(0) == '0' || Integer.parseInt(t) == 0) {
return false;
}
i += Integer.parseInt(t);
j = k;
}
return i == m && j == n;
}
}

• // 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:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
i = j = 0
m, n = len(word), len(abbr)
while i < m:
if j >= n:
return False
if word[i] == abbr[j]:
i, j = i + 1, j + 1
continue
k = j
while k < n and abbr[k].isdigit():
k += 1
t = abbr[j:k]
if not t.isdigit() or t[0] == '0' or int(t) == 0:
return False
i += int(t)
j = k
return i == m and 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


• func validWordAbbreviation(word string, abbr string) bool {
i, j := 0, 0
m, n := len(word), len(abbr)
for i < m {
if j >= n {
return false
}
if word[i] == abbr[j] {
i++
j++
continue
}
k := j
for k < n && abbr[k] >= '0' && abbr[k] <= '9' {
k++
}
if k == j || abbr[j] == '0' {
return false
}
x, _ := strconv.Atoi(abbr[j:k])
if x == 0 {
return false
}
i += x
j = k
}
return i == m && j == n
}