2021-02-22] Longest Word in Dictionary through Deleting

간만에 Blog를 작성하는 시간을 갖게 되었다.

 

잠시 필자의 근황 공유를 하자면, 이직준비를 하며 인터뷰를 봤었고, 개인적으로 안 좋은 일도 겹쳐 한동안

 

leetcode 문제도 풀지 못하고, 글도 못 올렸었다.. 

 

그래도 가능하면 1일 1문제를 하려 했지만, 여간 멘탈을 잡기 힘들었달까. 오늘은 재택근무를 하면서

 

시간이 나서 문제도 풀고 글도 쓸 수 있게 되었다. 다시 마음을 붙잡고 글을 잘 쓸 수 있으면 좋겠다.

 

오늘의 문제:

leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/587/week-4-february-22nd-february-28th/3649/

 

문제를 잘 읽고 예제를 보도록 하자.

 

입력값으로 주어지는 s와 d가 있다. s 안에서 문자를 제거하면서 ( 순서를 바꿀수는 없다. )

 

list 안의 문자열을 만들 수 있는 가장 긴 길이의 문자열을 반환하는 것이다.

 

만약 길이가 같은 문자열이라면, 사전순으로 정렬하여 가장 앞의 값을 ( a-z ) 보여주면 된다. ( 예제 2 )

 

예제 1)

ale는 ' a bpcp le a ' 앞 처럼 지워서 만들 수 있다. 만들 수 있기 때문에, 정답 후보군에 들어갈 수 있음

apple은 ' a b p c ple a ' = 가능 -> 정답 후보군 길이가 더 길어서 교체  ( ale -> apple )

monkey는 m이 s에 없기때문에 바로 out 

plea 는 ' abpc plea ' = 가능 -> 정답 후보군에 들지만 길이가 작아서 유지 ( apple > plea )

 

즉 정답은 'apple'

 

아래 코드를 보며 다시 한번 이해해 보도록 하면 좋겠다.

 

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        check=False
        checks = list(s)
        temp=""
        ans=""
        for idx in d:
            for dd in idx:
                if dd in checks:
                    #print(checks)
                    cutidx=checks.index(dd)
                    checks=checks[cutidx+1:]
                    #checks.remove(dd)
                    check=True
                    temp=idx
                else:
                    check=False
                    break
            if check:
                #print(temp,ans)
                if len(temp)>len(ans):
                    ans=temp
                elif len(temp)==len(ans) and temp<ans:
                    ans=temp                 
            check=False
            checks=list(s)
        return ans