README_EN.md

408. Valid Word Abbreviation

中文文档

Description

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

• "s10n" ("s ubstitutio n")
• "sub4u4" ("sub stit u tion")
• "12" ("substitution")
• "su3i1u2on" ("su bst i t u ti on")
• "substitution" (no substrings replaced)

The following are not valid abbreviations:

• "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
• "s010n" (has leading zeros)
• "s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Example 2:

Input: word = "apple", abbr = "a2e"
Output: false
Explanation: The word "apple" cannot be abbreviated as "a2e".

 

Constraints:

• 1 <= word.length <= 20
• word consists of only lowercase English letters.
• 1 <= abbr.length <= 10
• abbr consists of lowercase English letters and digits.
• All the integers in abbr will fit in a 32-bit integer.

Solutions

Python3

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

Java

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

C++

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        int m = word.size(), n = abbr.size();
        while (i < m) {
            if (j >= n) {
                return false;
            }
            if (word[i] == abbr[j]) {
                ++i;
                ++j;
                continue;
            }
            int k = j;
            while (k < n && isdigit(abbr[k])) {
                ++k;
            }
            string t = abbr.substr(j, k - j);
            if (k == j || t[0] == '0') {
                return false;
            }
            int x = stoi(t);
            if (x == 0) {
                return false;
            }
            i += x;
            j = k;
        }
        return i == m && j == n;
    }
};

Go

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
}

...