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

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 \times 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 \geq m\) or \(word[i] \neq 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)\).

Python3JavaC++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

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

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

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
}

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

Comments