Open seungriyou opened 7 months ago
https://leetcode.com/problems/word-pattern/
easy 문제이지만 acceptance가 무려 40%대 초반인 문제! 면접에서 라이브 코딩용으로 아주 좋은 문제인 것 같다 😢
특히 2-Dict 접근법은 금방 가능할 것 같은데, 1-Dict 접근법은 불가능할까? 라는 질문에 면접관 앞에서 곧바로 답을 떠올리기 어려울 듯...
ptos와 stop 양방향 dict를 기록해가며, 두 dict와 일치하지 않은 p & s가 등장하면 곧바로 False를 반환하도록 한다.
ptos
stop
dict
p
s
False
ptos와 stop 중 하나의 dict만 사용할 수도 있다. 하지만 하나만 사용하면 반대를 확인할 수 없다.
예를 들어 stop을 사용한다고 하면, p는 이전에 등장했으나 s가 다른 경우(즉, False 반환해야 하는 경우)를 잡을 수 없는 것이다.
다음과 같은 케이스를 생각해보자.
pattern = "abba" , ss = ["dog", "cat", "cat", "fish"]
p = 마지막 "a", s = "fish" 일 때를 가정해보면, p는 처음에 이미 등장했으나, 현재 s가 처음의 s인 "dog"가 아닌 "fish"이므로 False를 반환해야 하는데, 이를 잡을 수 없는 것이다.
"a"
"fish"
"dog"
따라서 미리 pattern과 ss의 종류의 개수가 같은지 확인함으로써 이러한 경우를 사전에 잡아야 한다.
pattern
ss
O(n)
easy 문제이지만 acceptance가 무려 40%대 초반인 문제! 면접에서 라이브 코딩용으로 아주 좋은 문제인 것 같다 😢
특히 2-Dict 접근법은 금방 가능할 것 같은데, 1-Dict 접근법은 불가능할까? 라는 질문에 면접관 앞에서 곧바로 답을 떠올리기 어려울 듯...
Approach
Idea 1: 2-Dict
ptos와stop양방향dict를 기록해가며, 두dict와 일치하지 않은p&s가 등장하면 곧바로False를 반환하도록 한다.Idea 2: 1-Dict 💡
ptos와stop중 하나의dict만 사용할 수도 있다. 하지만 하나만 사용하면 반대를 확인할 수 없다.예를 들어
stop을 사용한다고 하면,p는 이전에 등장했으나s가 다른 경우(즉,False반환해야 하는 경우)를 잡을 수 없는 것이다.다음과 같은 케이스를 생각해보자.
p= 마지막"a",s="fish"일 때를 가정해보면,p는 처음에 이미 등장했으나, 현재s가 처음의s인"dog"가 아닌"fish"이므로False를 반환해야 하는데, 이를 잡을 수 없는 것이다.따라서 미리
pattern과ss의 종류의 개수가 같은지 확인함으로써 이러한 경우를 사전에 잡아야 한다.Complexity
O(n)O(n)