s라는 소문자 알파벳 문자열이 있고 'pairs'라는 쌍 목록도 있다고 가정합니다. 쌍의 각 요소에는 문자 'a'와 'b'가 동일한 것으로 간주되는 두 개의 문자열 [a, b]가 있습니다. [a, b] 및 [b, c]와 같은 두 쌍이 있는 경우 및 b는 또한 b와 c가 동일하므로 및 c도 동일하다고 말할 수 있습니다. 그리고 어떤 값이나 b는 그 자신과 동등합니다. 주어진 등가 관계로 s가 회문인지 아닌지 확인해야 합니다.
따라서 입력이 s ="raceckt" 쌍 =[["r", "t"], ["a", "k"], ["z", "x"]]인 경우 출력은 beTrue, "a" ="k", "r" ="t"이므로 문자열은 회문인 "racecar"가 될 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- g :=목록에 중복 요소가 포함될 수 있는 그래프의 인접 목록
- G :=중복 요소를 포함하지 않는 그래프의 인접 목록
- 각 x, y 쌍에 대해 수행
- g[x] 끝에 x 삽입
- g[y] 끝에 y 삽입
- g[x] 끝에 y 삽입
- g[y] 끝에 x 삽입
- dfs() 함수를 정의합니다. 시간이 걸립니다.
- 지금까지 삽입
- g[a]의 각 요소에 대해 do
- 요소가 so_far에 없으면
- dfs(요소, 지금까지)
- 요소가 so_far에 없으면
- 기본 방법에서 다음을 수행합니다. -
- g의 각 키에 대해 다음을 수행합니다.
- dfs(키, G[키])
- 0~(s / 2의 크기) 범위에 있는 i에 대해
- s[i]가 s[size of s -1-i] 또는 (s[i]가 G[s[size of s - 1-i]] 또는 s[-1 - i]인 경우 G[s[i]]) 에서
- 다음 반복으로 이동
- 그렇지 않으면
- 거짓을 반환
- s[i]가 s[size of s -1-i] 또는 (s[i]가 G[s[size of s - 1-i]] 또는 s[-1 - i]인 경우 G[s[i]]) 에서
- 참 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def solve(s, pairs): g = defaultdict(list) G = defaultdict(set) for x, y in pairs: g[x].append(x) g[y].append(y) g[x].append(y) g[y].append(x) def dfs(a, so_far): so_far.add(a) for elem in g[a]: if elem not in so_far: dfs(elem, so_far) for key in g: dfs(key, G[key]) for i in range(0, len(s) // 2): if s[i] == s[-1 - i] or (s[i] in G[s[-1 - i]] or s[-1 - i] in G[s[i]]): continue else: return False return True s = "raceckt" pairs = [["r", "t"], ["a", "k"], ["z", "x"]] print(solve(s, pairs))
입력
"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]
출력
True