내일은 알고리즘

https://leetcode.com/problems/is-subsequence/

Subsequence는 어떤 String에서 임의의 문자들을 삭제했을때 만들어지는 String이라고 합니다.

s가 t의 Subsequence인지 묻는 문제입니다.

문제 자체는 그리디한 느낌으로 s의 문자들을 차례대로 t에서 찾으면 해결됩니다.

다만 제 풀이코드 기준에서 s와 t의 길이에 따라 index가 범위를 넘어가는 경우가 있어서 예외처리해 주었습니다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if(len(s) > len(t)):
            return False
        if(len(s) == 0):
            return True

        idx = 0
        for i in t:
            if(i == s[idx]):
                idx += 1
            if(len(s) == idx):
                return True
        return False

input = [["abc", "ahbgdc"],["axc", "ahbgdc"]]

for i in input:
    print(Solution().isSubsequence(i[0],i[1]))

https://leetcode.com/problems/isomorphic-strings/

상당히 낯선 단어인데 Isomorphic은 동형사상이라는 뜻이라고 합니다.

Isomorphic String은 두 String의 형태가 닮아있는 것을 말하는데요. 예를 들어 glass와 shell이 동형관계입니다.

두 단어는 생김새가 전혀 다르지만 알파벳이 등장하는 순서대로 번호를 매기면 12344, 12344로 구조가 같음을 알 수 있습니다.

반대로 banana와 canada는 단어 생긴건 비슷하지만 번호를 매기면 123232와 123242로 차이가 있습니다.

문제에서 주어진 String을 앞에서부터 읽어가며 처음 만나는 알파벳인 경우 Dictionary에 Index값을 넣어주고, 이미 만났던 알파벳인 경우 Index값을 비교해 같은 구조인지 체크해줬습니다.

물론 알파벳의 내용은 다르므로 Dictionary를 두개 만들어서 따로 저장했습니다.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sDict = {}
        tDict = {}
        idx = 0

        for i in range(0,len(s)):
            if(not (s[i] in sDict) and not (t[i] in tDict)):
                sDict[s[i]] = idx
                tDict[t[i]] = idx
                idx += 1
            elif(s[i] in sDict and t[i] in tDict):
                if(sDict[s[i]] != tDict[t[i]]):
                    return False
            else: 
                return False
        
        return True

input = [["egg","add"],["foo","bar"],["paper","title"]]

for i in input:
    print(Solution().isIsomorphic(i[0],i[1]))