[LeetCode 316] Remove Duplicate Letters (RE 다른풀이)

https://leetcode.com/problems/remove-duplicate-letters/

Remove Duplicate Letters - LeetCode

 

 

 

Think

재귀는 많이 연습해야 겠다..

함수 만들어서 재귀로 푸는 거에 쫄지 말기.

스택으로 푸는 법도 다시 풀어보기.

 

Solution

1. 재귀

class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        #현재의 전체 집합에서 정렬된 앞에서부터 한글자씩 체크
        for char in sorted(set(s)) :
            
            #체크할 char의 suffix집합 생성(슬라이싱)
            suffix = s[s.index(char):]
            
            #전체집합 == suffix집합이면 suffix만 남기고 분리 후 return (suffix에서 현재 char는 삭제)
            # != 이면 return없이 for문 돌며 다음 char체크
            if set(s) == set(suffix) :
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        
        #재귀이므로 이 값이 마지막에 붙어서 나옴. 붙일 게 없으니 빈값으로 함.
        #왜 이게 맨 뒤에 붙이서 나오지???? return 하자마자 함수 실행 끝해야 하는 거 아닌가
        return ''

2. 스택

-

 

 

Get

• 파이썬 집합 자료형 set 
  • set(...) 으로 생성
  • 중복제거
• string.index(char) : 문자열에서 특정 문자의 인덱스 찾기. char말고 string을 넣어도 가능함
• string.find(...) : index()와 거의 같은 기능을 함. 
• index()와 find()의 차이는 찾는 값이 존재하지 않을 때
  • index : ValueError 에러 뱉음. try-catch문으로 감싸서 사용할 것
  • find : -1 을 반환함