Question

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)$.

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