leetcode 205 Isomorphic Strings
'''
leetcode 205 Isomorphic Strings
Isomorphic : 동형사상
동형일 경우는 어떤경우인가 ? s의 문자를 대체하여 t를 얻을 수 있다면 두 문자열 s와 t는 동형이다.
문자의 모든 발생은 문자의 순서를 유지하면서 다른 문자로 대체되어야 합니다.
두 개의 문자는 동일한 문자에 매핑할 수 없지만, 문자는 그 자체로 매핑할 수 있습니다.
즉, 하나의 문자는 하나에만 매핑이 가능함.
egg 와 add의 경우,
e => a로
g => d로 바꾸면 똑같아진다.
연속되는 문자열의 경우 또한 고려해야한다.
foo와 bar의 경우,
o가 연속되는 경우가 있고 동일 위치에 bar는 연속되는 두글자가 존재하지 않는다.
이는 동형이 아님을 의미한다.
1.문자열의 길이를 확인한다.
2.연속되는 문자열이 있는 경우 어디부터 어디까지 연속되는지 위치를 확인해야한다.
문자열이 연속되는 걸 확인하기 위해서 문자열을 숫자로 치환한다.
즉, 문자열을 숫자로 치환한 딕셔너리를 이용하여 각각의 문자열을 숫자로 변경한 문자열을 비교한다.
'''
def isIsomorphic(s, t):
new_s = ""
new_t = ""
if len(s) != len(t):
return False
dict_a = dict.fromkeys(list(s),-1)
dict_b = dict.fromkeys(list(t),-1)
for idx,a in enumerate(dict_a):
dict_a[a] = idx
for idx,b in enumerate(dict_b):
dict_b[b] = idx
for a,b in zip(s,t):
new_s += " " + str(dict_a[a])
new_t += " " + str(dict_b[b])
return new_s == new_t
if __name__ == '__main__':
s = "abcdefghijklmnopqrstuvwxyzva"
t = "abcdefghijklmnopqrstuvwxyzck"
print(isIsomorphic(s,t))해당 문제를 풀면서 두가지 테스트 케이스를 통해 주의해야할 점 두가지를 알아냈다.
파이썬 버전 3.6 이후부터는 입력한 순서를 보장하는 딕셔너리가 기본으로 제공되지만 이전 버전은 순서를 보장하는 딕셔너리가 기본으로 제공되지 않아서 orderedDict을 사용하여야 한다.
해당 케이스를 위한 테스트 케이스는 다음과 같다.
"paper"
"title"
리트코드와 내가 사용하는 파이참에서 코드는 똑같지만 다른 결과를 뱉어내길래 딕셔너리를 출력해서 보니, 순서 보장여부가 달랐고 orderedDict을 써야한다는 사실을 추론할 수 있었다.
다음 주의점은 현재 코드에서 테스트하고 있는 케이스이다. 처음에 작성한 코드는 공백을 주지 않아서 0123456.. 이런식으로 출력되어 10이 넘어갈 경우 해당 케이스를 통과하지 못했다. 이를테면 21이 2,1 로 인식할 수 있는 경우 말이다. 이러한 케이스를 위해
s = "abcdefghijklmnopqrstuvwxyzva"
t = "abcdefghijklmnopqrstuvwxyzck"
value값 사이에 공백을 넣어주었다.
leetcode 392 Is Subsequence
'''
leetcode 392 Is Subsequence
what is subsequence?
나머지 문자열의 상대적 위치를 방해하지 않고 문자 중 일부 혹은 공백을 삭제하여 원래 문자열에서 형성된 새로운 문자열을 말함.
그렇다면,
s = abc
t = ahbgdc
a(h)b(gc)c
이러한 식으로 사이에 들어간 문자열을 뺏을 때 s로 다시 되돌아와야 한다는 말!
'''
def isSubsequence(s,t):
id = 0
if s == "":
return True
for word in t:
if word == s[id]:
if id < len(s)-1:
id+=1
# --1--
else :
return True
if id < len(s)-1 :
# --2--
return False
if __name__ == '__main__':
s = "axc"
t = "ahbgdc"
print(isSubsequence(s,t))생각보다 간단한 문제였다.
what is subsequence?
나머지 문자열의 상대적 위치를 방해하지 않고 문자 중 일부 혹은 공백을 삭제하여 원래 문자열에서 형성된 새로운 문자열을 말한다.
테스트하면서 걸렸던 조건은 하나였다. 만약 주어진 문자열이 공백일 경우라면 ?
해당 경우에는 무조건 True이기 때문에 첫번째 조건으로 걸어두었다.
해당 조건이 왜 true인지는 문제의 이 부분을 참고하면 된다.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.
공백의 경우 사이에 모든 문자열이 들어갈 수 있기 때문에 무조건 true 값을 반환하는 것이다.
마지막으로 1,2번 조건문을 달아준 이유에 대해서도 서술해보면,
1번 조건문의 경우, id의 값이 하나씩 올라갈때 조건을 걸어주어 s 문자열이 끝나도 id 값이 1이 더해지지 않도록 구성했다.
즉, s의 길이가 3이기 때문에 id는 2까지 증가해야하는데 조건문을 걸어주지 않을 경우 3까지 증가하는 경우가 생긴다 해당 부분을 제거하기 위해 조건문을 걸어주었다.
다음 2번의 조건문의 경우, for문을 끝까지 순회한경우에 id의 값이 s의 길이 -1 를 충족하지 못한 경우 subsequence가 아닌 경우 False를 리턴해야하기 때문에 해당 조건문을 걸어주었다.
