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 $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ and the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ are $m <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi></math>$ and $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ respectively. We use two pointers $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ and $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ to point to the initial positions of the string $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ and the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ respectively, and use an integer variable $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ to record the current matched number in $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ .

Loop to match each character of the string $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ and the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ :

If the character $a b b r [j] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></math>$ pointed by the pointer $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ is a number, if $a b b r [j] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></math>$ is '0' and $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ is $0 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math>$ , it means that the number in $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ has leading zeros, so it is not a valid abbreviation, return false; otherwise, update $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ to $x \times 10 + a b b r [j] - ‘ 0' <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi><mo>\times</mo><mn>10</mn><mo>+</mo><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo><mo>-</mo><mo data-mjx-pseudoscript="true">‘</mo><msup><mn>0</mn><mo data-mjx-alternate="1">'</mo></msup></math>$ .

If the character $a b b r [j] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></math>$ pointed by the pointer $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ is not a number, then we move the pointer $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ forward by $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ positions at this time, and then reset $x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>$ to $0 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math>$ . If $i \geq m <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi><mo>\geq</mo><mi>m</mi></math>$ or $w o r d [i] \neq a b b r [j] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>\neq</mo><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></math>$ at this time, it means that the two strings cannot match, return false; otherwise, move the pointer $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ forward by $1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math>$ position.

Then we move the pointer $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ forward by $1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math>$ position, repeat the above process, until $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ exceeds the length of the string $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ or $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ exceeds the length of the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ .

Finally, if $i + x <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi><mo>+</mo><mi>x</mi></math>$ equals $m <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi></math>$ and $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ equals $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ , it means that the string $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ can be abbreviated as the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ , return true; otherwise return false.

The time complexity is $O (m + n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mi>n</mi><mo stretchy="false">)</mo></math>$ , where $m <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi></math>$ and $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ are the lengths of the string $w o r d <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi></math>$ and the string $a b b r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mi>b</mi><mi>r</mi></math>$ respectively. The space complexity is $O (1) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></math>$ .

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

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

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

408 - Valid Word Abbreviation

408. Valid Word Abbreviation

Description

Solutions

All Problems

All Solutions

Welcome to Subscribe On Youtube

408. Valid Word Abbreviation

Description

Solutions

All Problems

All Solutions