LeetCode 408 Valid Word Abbreviation

LeetCode

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.

题目大意：

验证第二字符串是否第一字符串的一个种简写形式，用数字代替字符串部分长度

解题思路：

Easy题

解题步骤：

注意事项：

用内外while循环如quicksort的不推荐的算法，内循环的条件一定要复制外循环的条件j < len(abbr)
题目条件不能含前缀0，包括0本身，若数字第一位为0，就返回False

Python代码：

def validWordAbbreviation(self, word: str, abbr: str) -> bool:
	i, j, num = 0, 0, 0
	while i < len(word) and j < len(abbr):
		num_str = ''
		while j < len(abbr) and abbr[j].isdigit(): # remember j < len(abbr)
			num_str += abbr[j]
			j += 1
		if num_str:
			if num_str[0] == '0': # remember
				return False
			i += int(num_str)
		elif word[i] != abbr[j]:
			return False
		else:
			i += 1
			j += 1
	return False if i != len(word) or j != len(abbr) else True

算法分析：

时间复杂度为O(n)，空间复杂度O(n)