LeetCode 0408. Valid Word Abbreviation Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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

Solution 1: Simulation

We can directly simulate character matching and replacement.

Assume the lengths of the string word and the string abbr are m and n respectively. We use two pointers i and j to point to the initial positions of the string word and the string abbr respectively, and use an integer variable x to record the current matched number in abbr.

Loop to match each character of the string word and the string abbr:

If the character abbr[j] pointed by the pointer j is a number, if abbr[j] is '0' and x is 0, it means that the number in abbr has leading zeros, so it is not a valid abbreviation, return false; otherwise, update x to x × 10 + abbr[j] - '0'.

If the character abbr[j] pointed by the pointer j is not a number, then we move the pointer i forward by x positions at this time, and then reset x to 0. If i ≥ m or word[i] ≠ abbr[j] at this time, it means that the two strings cannot match, return false; otherwise, move the pointer i forward by 1 position.

Then we move the pointer j forward by 1 position, repeat the above process, until i exceeds the length of the string word or j exceeds the length of the string abbr.

Finally, if i + x equals m and j equals n, it means that the string word can be abbreviated as the string abbr, return true; otherwise return false.

The time complexity is O(m + n), where m and n are the lengths of the string word and the string abbr respectively. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def validWordAbbreviation(self, word: str, abbr: str) -> bool: m, n = len(word), len(abbr) i = j = x = 0 while i < m and j < n: if abbr[j].isdigit(): if abbr[j] == "0" and x == 0: return False x = x * 10 + int(abbr[j]) else: i += x x = 0 if i >= m or word[i] != abbr[j]: return False i += 1 j += 1 return i + x == m and j == n(code-box)

class Solution { public boolean validWordAbbreviation(String word, String abbr) { int m = word.length(), n = abbr.length(); int i = 0, j = 0, x = 0; for (; i < m && j < n; ++j) { char c = abbr.charAt(j); if (Character.isDigit(c)) { if (c == '0' && x == 0) { return false; } x = x * 10 + (c - '0'); } else { i += x; x = 0; if (i >= m || word.charAt(i) != c) { return false; } ++i; } } return i + x == m && j == n; } }(code-box)

class Solution { public: bool validWordAbbreviation(string word, string abbr) { int m = word.size(), n = abbr.size(); int i = 0, j = 0, x = 0; for (; i < m && j < n; ++j) { if (isdigit(abbr[j])) { if (abbr[j] == '0' && x == 0) { return false; } x = x * 10 + (abbr[j] - '0'); } else { i += x; x = 0; if (i >= m || word[i] != abbr[j]) { return false; } ++i; } } return i + x == m && j == n; } };(code-box)

func validWordAbbreviation(word string, abbr string) bool { m, n := len(word), len(abbr) i, j, x := 0, 0, 0 for ; i < m && j < n; j++ { if abbr[j] >= '0' && abbr[j] <= '9' { if x == 0 && abbr[j] == '0' { return false } x = x*10 + int(abbr[j]-'0') } else { i += x x = 0 if i >= m || word[i] != abbr[j] { return false } i++ } } return i+x == m && j == n }(code-box)

function validWordAbbreviation(word: string, abbr: string): boolean { const [m, n] = [word.length, abbr.length]; let [i, j, x] = [0, 0, 0]; for (; i < m && j < n; ++j) { if (abbr[j] >= '0' && abbr[j] <= '9') { if (abbr[j] === '0' && x === 0) { return false; } x = x * 10 + Number(abbr[j]); } else { i += x; x = 0; if (i >= m || word[i++] !== abbr[j]) { return false; } } } return i + x === m && j === n; }(code-box)