소문자로 된 문자열 s가 있다고 가정합니다. 다른 위치에서 s의 다른 부분 문자열이 있어야 하는 s의 모든 부분을 찾아야 합니다. 이는 취한 부분 문자열의 아나그램입니다. 사전순으로 하위 문자열 목록을 찾아야 합니다.
따라서 입력이 s ="abcba"와 같으면 출력은 ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba'가 됩니다. , 'bc', 'bcba', 'cb', 'cba'] 각각에 대해 문자열 자체에 있는 서로 다른 아나그램을 찾을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
res :=새 목록
-
L :=s
의 크기 -
범위 1에서 L에 있는 i에 대해 수행
-
smap :=빈 사전이고 모든 값은 목록 유형입니다.
-
범위 0에서 L - i에 있는 j에 대해 수행
-
cs :=인덱스 j에서 j + i-1까지 s의 부분 문자열]
-
k :=cs 항목을 정렬된 형식으로 결합한 후 문자열
-
smap[k]
끝에 cs를 삽입합니다.
-
-
smap의 각 키 k 및 값 v에 대해 수행
-
v>=2의 크기인 경우
-
v의 요소를 res에 삽입
-
-
-
-
정렬 후 res를 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from collections import defaultdict def solve(s): res = [] L = len(s) for i in range(1, L + 1): smap = defaultdict(list) for j in range(L - i + 1): cs = s[j : j + i] k = "".join(sorted(cs)) smap[k].append(cs) for k, v in smap.items(): if len(v) >= 2: res.extend(v) return sorted(res) s = "abcba" print(solve(s))
입력
"abcba"
출력
['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']