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
}

408 - Valid Word Abbreviation

408. Valid Word Abbreviation (Easy)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

408. Valid Word Abbreviation (Easy)

Solution 1.

All Problems

All Solutions