Leetcode: 문자열의 최대 공약수

문제 설명 1071. 문자열의 최대 공약수

두 문자열 s와 t에 대해 s = t + t + t + ... + t + t인 경우에만 "t가 s를 나눕니다"라고 말합니다(즉, t가 자신과 한 번 이상 연결됨).

두 개의 문자열 str1과 str2가 주어지면 x가 str1과 str2를 모두 나누는 가장 큰 문자열 x를 반환합니다.

나의 사고방식

leetcode에는 쉬운 문제로 표시되어 있지만 즉시 해결책을 찾기가 어려웠다는 점을 인정해야 합니다.

leetcode에서 제공하는 테스트 사례를 검토하고 이에 대해 설명하면서 혼란스러운 점을 설명하겠습니다.

테스트 케이스

입력: str1 = "ABCABC", str2 = "ABC"
출력: "ABC"

입력: str1 = "ABABAB", str2 = "ABAB"
출력: "AB"

문제 설명과 테스트 사례 1에서 두 문자열을 모두 얻을 수 있는 가장 큰 문자열("ABC")을 연결하여 출력해야 한다고 결정했습니다. (기본 문자열 "ABC" === str2 및 "ABC" + "ABC" === str1).

그러나 테스트 사례 2를 보면서 두 문자열을 모두 생성할 수 있는 가장 긴 문자열인 "ABAB"를 출력해야 한다는 점에서 내 이해가 올바르지 않다는 것을 빨리 깨달았습니다. 그러나 나는 코드로 뛰어들어 해결책을 찾기 시작했습니다. (신인실수?)

실패/성공

다음과 같은 경우에만 솔루션을 구상할 수 있었습니다.

1. 두 문자열의 GCD를 구합니다.
2. 가장 작은 문자열의 길이부터 GCD까지 반복
3. 가장 작은 문자열에서 현재 반복 값까지 하위 문자열을 가져옵니다.
4. 두 문자열 모두 해당 하위 문자열을 포함하는 경우 해당 하위 문자열을 답변으로 반환합니다.
5. 문자열이 없으면 ""를 반환합니다.

보시다시피 str1에 str2가 포함되어 있지만 다른 추가 문자도 포함되어 있는 문자열에 대한 내 솔루션은 실패했습니다. s = t + t + ... + t + t라는 요구 사항을 위반합니다.

Neetcode의 솔루션에 도움을 요청해야 했습니다. 내 문제를 빨리 이해했습니다.

1. 문자열 자체가 아닌 문자열 길이의 GCD를 찾고 있었습니다. 해당 문자열을 반복하여 남은 문자 없이 두 문자열을 모두 생성할 수 있는 문자열을 찾아야 합니다.

2. 왜 "ABAB"가 테스트 케이스 2의 답이 될 수 없는지 깨달았습니다:

• 두 문자열을 동일하게 나누는 x를 찾아야 합니다. 따라서 "ABAB"를 문자열로 사용하면 str2를 완전히 생성할 수 있지만 str1의 경우 "ABABABAB"으로 끝납니다. 2개의 "AB"가 초과되어 x를 결합하여 str1을 완전히 생성했다고 말할 수 없습니다.

• "ABAB" 길이는 4이고 "ABABAB" 길이는 6입니다. 두 문자열의 GCD = 2. 따라서 출력은 길이가 2인 문자열이어야 합니다.

출력

시간과 공간의 복잡성

시간 복잡성:

최악의 경우 Min(str1,str2)을 반복하고 str1과 str2를 다시 생성해야 전체 시간이 (str1.length + str2.length)가 됩니다. 복잡성은 O(min(str1,str2) * (str1.length + str2.length))

공간 복잡도:

O(1) 추가 공간이 필요하지 않습니다.

위 내용은 Leetcode: 문자열의 최대 공약수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!