925. Long Pressed Name

Long Pressed Name - LeetCode

입력하고자 하는 문자열 name과 name을 입력하려고 했는데 일부 문자가 여러 번 눌린 문자 typed가 주어진다.

typed에서 여러 번 눌린 문자를 제거했을 때 name으로 변환이 가능한지 판단하는 문제다.

 

예시

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Input: name = "leelee", typed = "lleeelee"
Output: true

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.

 

1. 구현

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:

        def make_trace(input_string):
            trace, index = [], 0
            while index < len(input_string):
                cur = input_string[index]
                temp = [cur]
                while index + 1 < len(input_string) and input_string[index + 1] == cur:
                    temp.append(cur)
                    index += 1
                trace.append("".join(temp))
                index += 1
            return trace

        def match(str1, str2):
            if str1 in str2:
                return True
            return False

        trace1, trace2 = make_trace(name), make_trace(typed)

        if len(trace1) != len(trace2):
            return False

        for i in range(len(trace1)):
            if not match(trace1[i], trace2[i]):
                return False

        return True

2개의 함수를 이용해 구현을 했다.

make_trace는 문자열을 같은 문자열끼리 split 한 문자열을 저장한 list를 반환한다.

match는 str1이 str2와 같거나 부분 문자열인 경우 True를 반환한다.

 

위 예제를 가지고 시뮬레이션하면 다음과 같다.

case1
name = "alex", typed = "aaleex"
make_trace(alex) -> [a,l,e,x]
make_trace(aaleex) -> [aa,l,ee,x]

match(a,aa) -> True
match(l,l) -> True
match(e,e) -> True
match(x,x) -> True
return True

case2
name = "saeed", typed = "ssaaedd"
make_trace(saeed) -> [s,a,ee,d]
make_trace(ssaaedd) -> [ss,aa,e,dd]

match(s,ss) -> True
match(a,aa) -> True
match(ee,e) -> False
match(d,dd) -> True
return False

결국 입력해야 하는 문자열을 여러 번 누른 경우에 생성되는 문자열이라면 같은 문자열끼리 끊었을 때 나오는 make_trace의 결과 배열의 길이가 같아야 한다. 그리고 끊었을 때 나오는 문자열은 반드시 원래 문자열과 같거나 원래 문자열이 부분 문자열이 여야 한다.

 

2. 최적화

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:

        i = 0
        for j in range(len(typed)):
            if i < len(name) and name[i] == typed[j]:
                i += 1
            elif j == 0 or typed[j - 1] != typed[j]:
                return False

        return i == len(name)

한 번의 선형 탐색으로 위에서 언급한 조건을 전부 체크할 수 있다.

 

직접 써 보면 감탄이 나오는 풀이.