파이썬에서 가장 긴 공통 부분 문자열
- 파이썬에서 가장 긴 공통 부분 문자열
- Python에서 루프를 사용하는 가장 긴 공통 부분 문자열
- 재귀를 사용하여 가장 긴 공통 부분 문자열 찾기
- 동적 프로그래밍을 사용하여 Python에서 가장 긴 공통 부분 문자열 찾기
- 결론
Python의 문자열은 다양한 작업을 수행하기 위해 일련의 문자를 저장합니다. 하위 문자열은 이러한 문자열의 일부입니다.
이 기사에서는 주어진 두 문자열 사이에서 가장 긴 공통 부분 문자열을 찾아야 하고 이에 대한 다양한 솔루션을 논의할 것입니다.
파이썬에서 가장 긴 공통 부분 문자열
부분 문자열은 주어진 문자열 내에서 연속적인 문자 시퀀스입니다. 길이에 상관없이 가능합니다.
주요 문제는 우리에게 두 개의 문자열이 제공되었고 주어진 문자열 사이에 공통적이며 가능한 모든 공통 하위 문자열 중에서 가장 길어야 하는 하위 문자열을 찾아야 한다는 것입니다.
Input: str1 = "HaveAAppleRegularly"
str2 = "HaveAnAnApple"
Output: "Apple"
위의 예에서는 주어진 문자열 "Have"와 "Apple" 사이에 두 개의 공통 하위 문자열이 있습니다. 그러나 "Apple" 부분 문자열의 길이가 나머지 부분 문자열 중에서 가장 길기 때문에; 따라서 결과로 표시됩니다.
이 문제는 재귀 및 동적 프로그래밍과 같은 다양한 개념을 사용하여 해결할 수 있습니다.
Python에서 루프를 사용하는 가장 긴 공통 부분 문자열
루프를 사용하여 문자열을 반복할 수 있습니다. 루프를 사용하여 여기에서 문자열을 반복하고 주어진 두 문자열 사이에서 가장 긴 공통 부분 문자열을 찾을 수 있습니다.
이 접근 방식에서는 for 및 while 루프를 모두 사용합니다. 다음은 Python에서 가장 긴 공통 부분 문자열을 찾기 위해 따라야 하는 단계입니다.
-
첫 번째 문자열의 모든 부분 문자열을 찾습니다.
-
첫 번째 문자열의 현재 부분 문자열도 두 번째 문자열의 부분 문자열인지 확인합니다.
-
두 부분 문자열이 모두 일치하면 길이를 특정 변수에 저장하고 이 변수를 계속 업데이트합니다.
-
마지막으로 부분 문자열의 길이를 저장하는 변수에 원하는 결과가 포함되어 인쇄됩니다.
코드 예:
str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result = 0
for i in range(len(str1)):
for j in range(len(str2)):
k = 0
while (
(i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]
):
k = k + 1
result = max(result, k)
print("Length of the longest common substring is:", result)
출력:
Length of the longest common substring is: 7
문자열의 모든 하위 문자열은 O(n^2) 시간으로 계산할 수 있지만 현재 하위 문자열이 두 번째 문자열의 하위 문자열과 일치하는지 확인하는 데 O(m) 시간이 걸립니다. 위의 접근 방식에 대한 시간 복잡도는 O(n^2 * m)입니다. 여기서 n과 m은 각각 주어진 두 문자열의 길이입니다.
그러나 솔루션을 달성하기 위해 추가 공간을 차지하지 않았기 때문에 위 솔루션의 공간 복잡도는 O(1)입니다.
재귀를 사용하여 가장 긴 공통 부분 문자열 찾기
재귀는 자신을 호출하는 함수를 나타냅니다. 재귀에서 당면한 문제에 대한 기본 사례와 선택 다이어그램이 필요합니다.
아래 단계에 따라 Python에서 가장 긴 공통 부분 문자열을 찾습니다.
-
가장 긴 공통 부분 문자열을 찾는 주어진 문제에서 가능한 가장 작은 입력은 길이가
0인 문자열이 될 수 있습니다. 따라서 기본 케이스는 입력의 길이가0인지 확인하고 함수는0을 반환해야 합니다. -
이제 두 문자열의 마지막 문자를 비교합니다. 그러면 두 문자가 일치하거나 서로 일치하지 않는 두 가지 경우가 발생합니다.
-
주어진 각 문자열의 마지막 문자가 일치하면 나머지 문자열을 재귀적으로 호출해야 합니다. 따라서 두 문자열의 길이를
1로 줄이고 여기에 1을 더하여 문자열의 길이를 계산합니다. -
그러나 문자가 일치하지 않으면 길이가
1만큼 감소하는 첫 번째 문자열에 대해 재귀 호출이 수행된 다음1만큼 길이를 줄이는 두 번째 문자열에 대한 재귀 호출이 수행됩니다. -
두 호출 사이의 최대 길이인 길이를 결과로 사용합니다.
코드 예:
def LCS(s1, s2, n, m):
if n == 0 or m == 0:
return 0
if s1[n - 1] == s2[m - 1]:
return 1 + lcs(s1, s2, n - 1, m - 1)
else:
return max(lcs(s1, s2, n, m - 1), lcs(s1, s2, n - 1, m))
s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
출력:
Length of the longest common substring is: 7
위 솔루션의 시간 복잡도는 O(3^(m+n))이고 공간 복잡도는 O(m+n)입니다.
동적 프로그래밍을 사용하여 Python에서 가장 긴 공통 부분 문자열 찾기
동적 프로그래밍의 기본 아이디어는 두 문자열의 모든 부분 문자열에 대한 길이를 찾고 각각의 길이를 테이블에 저장하는 것입니다. 재귀를 사용하기 때문에 큰 입력의 경우 재귀 스택이 계속 증가하기 때문에 스택 오버플로 오류가 발생할 가능성이 있습니다.
테이블을 형성하고 각 부분 문자열에 대한 결과를 계속 저장하는 동적 프로그래밍 개념을 소개합니다. 재귀에서 사용한 것과 동일한 알고리즘이 일부 변경에도 사용됩니다.
이제 우리는 파이썬에서 가장 긴 공통 부분 문자열을 찾는 단계에 대해 논의할 것입니다.
-
먼저 테이블의 첫 번째 열과 첫 번째 행을 초기화합니다. 이 셀은 재귀의 기본 조건에서 본 것처럼
0값으로 초기화됩니다. -
우리는 논리에 재귀 호출 대신 루프를 사용합니다.
-
루프 내에서 두 문자열의 마지막 문자가 일치하면 특정 셀의 길이를
1만큼 늘립니다. -
그렇지 않으면 특정 셀의 인접한 행과 열까지 최대 길이를 저장합니다.
-
마지막으로 결과는 테이블의 마지막 위치에 저장됩니다. 따라서
dp[m][n]을 반환합니다.
코드 예:
def LCS(X, Y, m, n):
dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
for i in range(m + 1):
for j in range(n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
출력:
Length of the longest common substring is: 7
우리 솔루션에는 두 개의 루프만 있으므로 위 솔루션의 시간 복잡도는 O(m*n)입니다. 결과를 저장할 테이블을 구성하여 추가 공간을 사용하고 있습니다.
위 솔루션의 공간 복잡도는 O(m*n)입니다.
결론
우리는 주어진 두 문자열 사이에서 가장 긴 공통 부분 문자열을 찾는 세 가지 다른 접근 방식을 배웠습니다. 순진한 접근 방식인 첫 번째 접근 방식은 세 개의 루프를 사용하여 주어진 문자열의 모든 하위 문자열을 찾고 모든 하위 문자열 중에서 가장 긴 문자열을 확인합니다.
두 번째 접근 방식은 재귀를 사용하는 반면, 세 번째 접근 방식은 동적 프로그래밍을 사용하여 Python에서 가장 긴 공통 부분 문자열을 찾습니다. 세 번째 접근 방식은 이 문서에서 논의된 모든 솔루션 중에서 문제를 해결하는 데 가장 빠르며 선호되어야 합니다.