leetcode_1202. 문자열 의 요 소 를 교환 합 니 다.
제목
2. 문제 풀이 사고
코드
제목
문자열 하나 드릴 게 요. s, 그리고 이 문자열 의 '색인 쌍' 배열 pairs, 그 중 pairs[i] = [a, b] 문자열 의 두 색인 을 표시 합 니 다.
너 는 임의로 여러 번 교환 할 수 있다. pairs 색인 에 있 는 임의의 문자 입 니 다.
몇 번 의 교환 을 거 친 후, s 로 되 돌아 갑 니 다. 사전 순서에 따라 가장 작은 문자열 로 변 할 수 있 습 니 다.
예시 1:
입력: s = "dcab", pairs = [0, 3], [1, 2] 출력: "bacd" 설명: 교환 s [0] 와 s [3], s = "bcad" 교환 s [1] 와 s [2], s = "bacd"
예시 2:
입력: s = "dcab", pairs = [0, 3], [1, 2], [0, 2] 출력: "abcd" 해석: 교환 s [0] 와 s [3], s = "bcad" 교환 s [0] 와 s [2], s = "acbd" 교환 s [1] 와 s [2], s = "abcd"
예시 3:
입력: s = "cba", pairs = [0, 1], [1, 2] 출력: "abc" 해석: 교환 s [0] 와 s [1], s = "bca" 교환 s [1] 와 s [2], s = "bac" 교환 s [0] 와 s [1], s = "abc"
알림:
1 <= s.length <= 10^5 0 <= pairs.length <= 10^5 0 <= pairs[i][0], pairs[i][1] s 소문 자 만 들 어 있 습 니 다.
2. 문제 풀이 사고
그리고 집합 을 찾 으 려 면 각 구간 의 최소 색인 과 최대 값 을 찾 아야 합 니 다. 여러 구간 의 시작 점 이 키 값 인 목록 이 나타 날 수 있 습 니 다. 목록 에는 연결 가능 한 노드 가 있 습 니 다.
각 구간 목록 에 대응 하 는 문 자 를 정렬 한 다음 색인 에 대응 하 는 위치 에 놓 습 니 다. 즉, 사전 순서에 따라 가장 작은 문자열 입 니 다.
코드
from collections import defaultdict
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: list) -> str:
if len(pairs) == 0:
return s
p = [-1 for _ in range(len(s))]
def find(x):
if p[x] < 0:
return x
return find(p[x])
def merge(x1, x2):
if x1 == x2:
return
if x1 < x2:
p[x2] = x1
else:
p[x1] = x2
for pair in pairs:
x1 = find(pair[0])
x2 = find(pair[1])
merge(x1, x2)
x_dict = defaultdict(list)
for i in range(len(s)):
x = find(i)
x_dict[x].append(i)
res = ['' for _ in range(len(s))]
for k, list_v in x_dict.items():
s_in_list_v = [s[i] for i in list_v]
s_in_list_v.sort()
for i in range(len(list_v)):
res[list_v[i]] = s_in_list_v[i]
return ''.join(res)
if __name__ == '__main__':
s = "dcab"
pairs = [[0,3],[1,2]]
ss = Solution()
ans = ss.smallestStringWithSwaps(s, pairs)
print(ans)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
