CareTim

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

풀이

처음에 문제를 보고 이해를 하지 못해서 다른 문제  LeetCode 290. Word Pattern 을 풀고나서 다시 돌아와서 봤는데.

문제가 거의 비슷하다는걸 알았다. 

전의 코드로 제출하니 통과가 되었다, 메모리가 다른사람보다 많이 먹는 거같아서 전에 봤던 다른사람의 코드를 find 활용해서 풀어봤다.

1. 딕셔너리 (해시맵 사용)

class Solution(object):
    def isIsomorphic(self, s, t):
        dict1 ={}						
        dict2 ={}								
        if len(s) != len(t):		
            return False
        for p,w in zip(s,t):		
            if p not in dict1 and w not in dict2:  
                dict1[p] = w			
                dict2[w] = p
            elif p in dict1 and w in dict2:	
                if dict1[p] != w or dict2[w] != p: 
                    return False
            else:				
                return False			
        return True

2. find로 각 인덱스가 같은 위치를 가르키는지 확인하는 코드 

class Solution(object):
    def isIsomorphic(self, s, t):
        if len(s) != len(t):  # 둘의 개수가 같은지 확인 
            return False
        
        for i in range(len(s)):
            if s.find(s[i]) != t.find(t[i]): # find함수로 각 인덱스의 위치가 동일한 위치를 짚는지 확인
                return False
        return True

find와 index 둘 다 사용 가능하다, 인덱스 위치를 찾을떄 가르키는 방향이 같은 곳인지 확인해주면 된다.-> 되는 이유: find함수는 index(인자) 를 통해서 인자의 인덱스 위치를 찾게되는데, 가르키는 위치가 다른 곳에 있거나 존재하지 않는다면 인덱스의 값이 동일하지 않기에 틀린지 옳은지 찾을 수 있다. 

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

풀이

각 자리수를 계속해서 제곱하여 숫자가 1이나온다면 행복한 수 , 아니라면 행복하지 않은 수다.

수는 계속해서 반복되며, 종료조건은 set에 반복되는 수가 동일하게 나타나면 각 자리의 수를 제곱해서 나오는 순환의 마지막에 도달했다고 판단해서 반복문을 종료시킨다.

class Solution(object):
    def isHappy(self, n):
        k = 0
        num_set =set()
        result = False
        while k not in num_set:
            str_n = str(n)
            num_set.add(n)
            num = 0
            for i in range(len(str_n)):
                num += int(str_n[i])**2
            if num == 1:
                result = True
                break
            k = num
            n= num
        return result

다른사람의 코드

def isHappy(self, n: int) -> bool:
        seen = set() # to store all the sum of square if digits
        while n != 1:
            sums = sum([int(digit)**2 for digit in str(n)]) # sum of square of digits
            if sums in seen: # if the sums in present in seen then it will be a endless loop
                return False
            n = sums
            seen.add(n)
        
        return True

요 사람도 set을 사용해서 계속해서 반복해서 값이 나오도록 만들었다. 

생각해보니 해시테이블로 풀어야하는데, set도 해시함수로 만들어진 구조이니 해시함수로 풀었다고 생각해도 되는거겠지..? ㅎㅎ 

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

풀이

전에 배웠던 아나그램, 동일한 원소로 이루어져있는 문자열을 아나그램이라고 한다.

사실 해시테이블을 통해서 만들 수도 있지만. 정렬과 set을 통해서 만들어봤다 ( set도 해시함수를 사용한다는걸 처음알았다)

리스트를 map함수를 통해 정렬시키고, 

class Solution(object):
    def groupAnagrams(self, strs):

        sort_list = list(map(sorted,strs))  # 각 원소 sorted 사용 (시간복잡도 폭발)


        strs_set = set()	# set에 각 값을 넣어 아나그램 개수 확인
        for i in sort_list:
            s = ''.join(i)			
            strs_set.add(s)
        
        result= [[] for __ in range(len(strs_set))]	# set저장된 원소의 개수만큼 정답리스트 생성

        strs_list = list(strs_set)	#index를 사용하기 위해 리스트 변환

        for i in range(len(sort_list)):	#strs리스트 순회
            result[strs_list.index(''.join(sort_list[i]))].append(strs[i])
       	#str_list 의 인덱스에 존재하는지 확인후 각 인덱스에 매핑되는 result인덱스 위치에 삽입
        return result

sorted함수를 사용하고 index함수까지 사용해서 시간복잡도가 높다..

다른사람의 코드 

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        letters_to_words = defaultdict(list)
        for word in strs:
            letters_to_words[tuple(sorted(word))].append(word)
        return list(letters_to_words.values())

아..그냥 defaultdict를 생성해서 순서를 넣어서 나가면 되는구나..ㅎㅎ.. 비슷한 방법이지만 속도가 빠르고 코드도 간단하다.  

딕셔너리에 리스트를 기본으로 밸류로 매핑되게 만들어준 후 , 각 문자열을 정렬 시킨 후, 정렬시킨 값을 키로 딕셔너리에 넣고 마지막에 list로 값을 변경시켜서 나가면 된다.

List 에서 특정원소를 찾기 위해서는 O(N)이 걸리지만 Set을 사용하게 된다면 set에서 원소검색은 O(1)의 시간복잡도를 가진다.

O(1)의 비결은?

해시테이블은 연관 배열(Associative array) 구조를 이용하여 키(Key)에 결과 값(value)을 저장하는 자료구조이다. 키와 값은 1:1로 연관되어 있고 키를 사용하여 값을 불러올 수 있다. 해당 키로부터 값을 도출하기 위해 해시함수가 사용된다. 

이는 Set에 활용되서 동일하게 해시함수를 거쳐서 동일하게 저장된다 대신 ! 

 Set에 원소를 저장할때는 기존의 리스트나 어레이처럼 앞, 뒤에 원소를 넣어주는 것이 아니라 해시함수를 거친 해시로 변경하여 저장소에 넣어준다는 것이다. 우리가 사용하는 set은 해시값으로 넣어주는게 아니라, 가변형으로 add나 remove로 값을 넣고 빼서 True와 False로 반환된다.

 Set에 존재하는지를 물어본다면 Set은 저장소의 앞 또는 뒤부터 검사를 시작하지 않는다. 특정원소를 해시함수를 통과 시킨 뒤 해당 해시가 저장소안에 있는지 없는지 검사만 하면 된다. 그렇기에 한번의 연산, O(1)만 일어나면 된다.

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

풀이

두 문자열의 패턴이 동일한지 찾는문제이다.

처음에는 같은 딕셔너리를 사용해서 같이 매칭되게 만들었지만, 테스트케이스에서 패턴의 단어가 중복되는 케이스가 있어서 두개의 딕셔너리를 사용해서 풀었다. 

class Solution(object):
    def wordPattern(self, pattern, s):
        dict1 ={}						# pattern 딕셔너리
        dict2 ={}						# s 딕셔너리
        ls= list((s.split(' ')))		# s문자열 공백기준으로 나누어서 리스트에 저장
        if len(pattern) != len(ls):		# pattern의 문자의 개수와 ls의 개수가 다르다면 False
            return False
        for p,w in zip(pattern,ls):		#zip함수로 문자열과 리스트를 순회
            if p not in dict1 and w not in dict2:  # 각 딕셔너리에 동시에 존재하지 않아야함
                dict1[p] = w			# dict1과 dict2에 각각 문자를 매핑시켜서 저장
                dict2[w] = p
            elif p in dict1 and w in dict2:	 # 둘 다 딕셔너리에 존재한다면 동일한지 체크
                if dict1[p] != w or dict2[w] != p: 
                    return False
            else:				# 어느곳에도 해당안된다면 ex) dict1에는 존재하나  
                return False			# dict2에는 없다면 False 반환 
        return True

다른사람의 코드

1.
def wordPattern(self, p: str, s: str) -> bool:
    words, w_to_p = s.split(' '), dict()

    if len(p) != len(words): return False
    if len(set(p)) != len(set(words)): return False # for the case w = ['dog', 'cat'] and p = 'aa'

    for i in range(len(words)):
        if words[i] not in w_to_p: 
            w_to_p[words[i]] = p[i]
        elif w_to_p[words[i]] != p[i]: 
            return False

    return True
    
 
 
 2.
 
 class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        arr = s.split()
        if len(arr) != len(pattern):
            return False
        
        for i in range(len(arr)):
            if pattern.find(pattern[i]) != arr.index(arr[i]):
                return False
        return True

1.

문자열을 공백기준으로 나누고 딕셔너리에 저장해서 사용했다. 

나는  w = ['dog', 'cat'] and p = 'aa' 의 사례에서 딕셔너리 하나로 사용하다가 생기는 문제 떄문에 딕셔너리를 2개 사용했지만 이 코드에서는 미리 글자수와 단어를 set으로 나누어서 미리 중복되지 않는 set의 원소들의 개수를 확인해서 미리 방지한다. 이런 방법도 있구나.

2.

인덱스를 찾아서 문자열이 동일한지 확인하는 방법이다. 심플하고 간단하다

각 인덱스를 for문으로 돌며 두 단어의 인덱스가 같은 곳을 가르키고 있는지 확인하는 방법이다.

find나 index 둘 중 하나만 사용해도 될 거 같다.

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

풀이

아나그램은 두 단어가 다르지만  동일한 알파벳과 개수로 구성된 단어이다 .

1.정렬로 푸는 방법 

문제를 보고 정렬시켜서 풀면 쉽겠다 생각하고 정렬함수를 사용하여 문제를 풀었다. 

문자열은 순회가 가능하니,  정렬 후 동일한지 확인해주는 방법으로 풀었다,

class Solution(object):
    def isAnagram(self, s, t):
        if sorted(s) == sorted(t):
            return True
        
        return False

2. 해시테이블로 풀는 방법

전에 풀었던 383. Ransom Note 문제에서 풀었던 s의 각 문자열을 for문으로 딕셔너리에 개수를 넣어주고,

t의 문자열을 for문으로 순회하며 -1시켜준다, 존재하지 않는다면 False를 반환한다.

 이후에 딕셔너리의 key value를 모두 꺼내서 value가 0이상이라면 False를 반환한다, .items() 함수를 사용안하고 그냥 dict.value()로 뽑아서 사용해도 상관없다. 

class Solution(object):
    def isAnagram(self, s, t):
        dict ={}
        for i in s:
            if i not in dict:
                dict[i] = 1
            else:
                dict[i]+=1
        
        for i in t:
            if i not in dict or dict[i]==0:
                return False
            dict[i]-=1
            
        for key,value in dict.items():
            if value >0:
                return False
        
        return True

다른사람의 코드 

1.    
    def isAnagram(self, s, t):
        dictionary = {}
        
        for i in s:
            if i in dictionary:
                dictionary[i] += 1
            else:
                dictionary[i] = 1

        for i in t:
            if i in dictionary:
                dictionary[i] -= 1
            else:
                return False

        for val in dictionary.values():
            if val != 0:
                return False
        
        return True
        
        
   2.
   class Solution(object):
    def isAnagram(self, s, t):
        return sorted(s.strip()) == sorted(t.strip())

둘 다 나랑 같은 생각을 했다..ㅎㅎ 

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

풀이

일정 문자열(magazine)이 주어지면 안에 들어있는 알파벳으로 ransomNote를 구성 할 수 있는지 확인하는 문제이다.

사실 여러가지 방법으로 풀 수 있지만 해시테이블을 사용해서 풀었다.

magzine에 담긴 문자열을 for문으로 순회하며 나오는 알파벳의 개수를 딕셔너리에 넣고  이후에 ransomNote를 for문으로 순회하며 나오는 횟수마다 딕셔너리에서 차감해주었다.

딕셔너리 대신 아스키코드로 변환해서 리스트 안에 넣어서 만들어도 괜찮을거같다.

class Solution(object):
    def canConstruct(self, ransomNote, magazine):

        dict ={} 			# 알파벳 횟수를 넣을 딕셔너리 생성
        for i in magazine: 	# 사용 할 수 있는 알파벳배열, 
            if i not in dict: # 딕셔너리에 없다면 키 값으로 저장, 
                dict[i] = 1
            else:
                dict[i]+=1 # 딕셔너리에 있다면 키의 밸류 +1
        
        for i in ransomNote:  # 만들어야 할 알파벳 배열
            if i not in dict or dict[i]==0: # 딕셔너리에 존재하지않거나, 0이라면 False 반환
                return False
            dict[i]-=1  	  # 존재한다면 값 -1 
        
        return True

다른사람의 풀이

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        for i in set(ransomNote):
            if ransomNote.count(i) > magazine.count(i):
                return False
        return True

문자열을 set으로 중복이 없게 만든 후, for문으로 뽑아내어 각각 카운트함수를 통해 개수를 비교한다.

음.. 시간복잡도를 생각해봤는데,영어 소문자 26개로만 주어진 가정하에 한다면 비슷할 거 같다, 만일 다른 문자까지 합쳐진다면 해시테이블을 쓰는게 맞다고 생각한다.

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

풀이

배열 안의 두 인덱스의 숫자가 동일하고, 각 인덱스의 위치를 뺄셈으로 연산하여 절대값으로 변환한 뒤 , 그 값이 k보다 작다면 True를 리턴하고 찾지 못한다면 Fasle를 반환하는 문제이다.

1. 문자열로 저장해서 사용하는 방법 

딕셔너리에 문자열로 인덱스가 2,3,4 이 중복된다하면 '234'로 넣어서 문자열을 for문으로 순회하는방법으로 코드를 짰다.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        dict = {}

        for i ,num in enumerate(nums):
            if num not in dict:
                dict[num] = str(i)
            else:
            	for j in dict[num]:
                if abs(i-j) <=k:
                    return True
                else:
                    dict[num]+=str(i)
            print(dict)
        return False

문제를 생각해보면 k보다 적어야 하기에 인덱스를 최신으로 갱신해주며 딕셔너리에 넣어주면 된다..

k보다 적어야하기에 계속해서 갱신해주면 순회하고있는 인덱스의 위치와 제일 가까운 위치가 된다.

간단한 방법인데 이때는 생각을 못했다..ㅋㅋ 시간복잡도도 위의 코드보다 더 좋다. 

2. 딕셔너리의 값을 최신 값으로 갱신해주기

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        dict = {}

        for i ,num in enumerate(nums):
            if num not in dict:
                dict[num] = i
            else:
                if i-dict[num] <=k:
                    return True
                else:
                    dict[num]=i
        return False
             

        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """

다른사람이 작성한 코드

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        myDict={}
        
        for i in range(len(nums)):
            
            if nums[i] in myDict and abs(i-myDict[nums[i]])<=k:
                return True
            myDict[nums[i]]=i
        return False

위의 코드와 거의 똑같은 방법으로 풀었다.

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    d = defaultdict(int)
    s = set()
    for i,x in enumerate(nums):
        if x in s and i-d[x]<=k:
            return True
        d[x] = i
        s.add(x)
    return False

set을 사용해서 각 인덱스의 문자열이 나왔는지 유무를 파악하고 딕셔너리에 넣어두었던 값을 갱신하며 찾는 방법이다.