408. Valid Word Abbreviation (Two Pointers, String)

링크 - https://leetcode.com/problems/valid-word-abbreviation/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

두 개의 포인터를 사용해서 문제를 풀면 된다. 각각 word와 abbr을 가리키면 되고, abbr에서 isnumeric()이 True가 되면 우리는 번호를 뽑아낸 뒤, word를 가리키는 포인터에 더하면된다. 그러면서 틀린 글자가 나오면 False, 아니면 두개의 포인터가 글자 끝까지 가면 True를 반환하면 된다.

Code

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        idx1, idx2 = 0, 0
        n1, n2 = len(word), len(abbr)
        while idx1 < n1 and idx2 < n2:
            if word[idx1] == abbr[idx2]:
                idx1 += 1
                idx2 += 1
            elif abbr[idx2] == "0":
                return False
            elif abbr[idx2].isnumeric():
                skip_idx = idx2
                while skip_idx < n2 and abbr[skip_idx].isnumeric():
                    skip_idx += 1
                idx1 += int(abbr[idx2:skip_idx])
                idx2 = skip_idx
            else:
                return False

        return idx1 == n1 and idx2 == n2

Complexity

Time Complexity: O(n) word와 abbr 모두를 돌아야 하므로 n1+n2 = n 만큼이 소요된다.

Space Complexity: O(1) 상수만 저장