230426/ leetcode / python/ 387. First Unique Character in a String, 383. Ransom Note, 242. Valid Anagram

 

Problem 1

First Unique Character in a String - LeetCode

---

Solution1

class Solution:
    def firstUniqChar(self, s: str) -> int:
        alphas = {}
        for i, ss in enumerate(s):
            if ss not in alphas:
                alphas[ss] = i
            else:
                alphas[ss] = -1
        
        valid_idxes = [idx for idx in alphas.values() if idx != -1]

        return -1 if not valid_idxes else min(valid_idxes)

 

• 딕셔너리 씀
• 딕셔너리밖에 생각 안 남
• 완탐?

1. 전체 순회하면서 중복으로 나타나면 -1 아니면 인덱스 딕셔너리에 넣어줌
2. 순회 끝나면 딕셔너리 value 중에 -1인 건 다 버림
3. 그게 비었으면 unique 하나도 없는 거고
4. 아니면 리스트 중에 min 값 반환함

 

 

Solution2

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i, ss in enumerate(s):
            if s.index(ss) == s.rindex(ss):
                return i
        
        return -1

 

• 보기엔 멋있어 보였는데 시간복잡도는 안 좋다
• 처음 푼 거는 걍 o(n)인데 두번째로 풀면 걍 계속 인덱스 찾음 o(n^2)

 

---

 

Problem2

Ransom Note - LeetCode

 

Solution1

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(magazine) < len(ransomNote):
            return False
        
        goal = {}
        
        for r in ransomNote:
            goal[r] = 1 + goal.get(r, 0)
        
        for m in magazine:
            if not goal:
                return True
            if m in goal:
                goal[m] = goal.get(m) - 1
                if goal[m] == 0:
                    del goal[m]
        
        return not goal

 

• 딕셔너리 씀

1. ransomNote 길이가 magazine 길이보다 크면 절대 못 만드니까 첨에 날려줌
2. ransomNote 순회하면서 몇번 나타났는지 goal 딕셔너리에 넣어줌
3. magazine 순회할 거임
   1. goal이 비어있으면 이미 다 완성한 거니까 True 반환
   2. m 이 goal 안에 있으면 -1 해주고 해준 게 0 이면 딕셔너리에서 삭제함
4. 전부 끝나고 딕셔너리가 비어있는지(완성했는지) 반환함

---

Problem3

Valid Anagram - LeetCode

 

Solution1

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        need = {}
        for ss in s:
            need[ss] = need.get(ss, 0) + 1

        for tt in t:
            if tt not in need or need[tt] <= 0:
                return False
            if tt in need:
                need[tt] = need.get(tt) - 1

        return True

 

• 딕셔너리 돌면서 깎으면서 비교함

Solution2

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        sorted_s = ''.join(sorted(s, key=lambda x: x.lower()))
        sorted_t = ''.join(sorted(t, key=lambda x: x.lower()))
        
        return sorted_s == sorted_t

 

• 걍 바로 정렬해서 같은지 비교함
• 시간복잡도 계산 아직도 어려움

 

 

두 코드 모두 문자열 s와 t가 서로 애너그램인지를 확인하는 기능을 합니다.

코드1에서는 딕셔너리를 사용하여 s 문자열의 각 문자가 몇 번 나타나는지를 기록한 후, t 문자열의 각 문자를 순회하면서 딕셔너리에 있는지 여부와 남은 개수를 확인합니다.
이 코드의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(k)입니다. 여기서 k는 s 문자열에서 고유한 문자의 수입니다.

코드2에서는 두 문자열을 모두 정렬하여 비교합니다.
Python의 내장 정렬 함수는 Timsort 알고리즘을 사용하며, 최악의 경우 시간 복잡도는 O(nlogn)입니다.
공간 복잡도는 문자열을 정렬하여 새로운 문자열을 생성하므로 O(n)입니다.

따라서 코드1은 공간 복잡도가 작고 문자열 길이가 작은 경우에 유리하며, 코드2는 문자열 길이가 큰 경우에 유리합니다.

 

 

*** 파이썬 sort 로 정렬하면 시간복잡도 nlogn이다 기억하기❗❗❗❗