Python으로 두 문자열에서 한 글자만 다른 부분 문자열 개수 구하기

문제 이해하기

두 문자열 s와 t가 주어졌다고 가정해 봅시다. 우리가 구해야 하는 값은, s에서 비어 있지 않은 부분 문자열을 하나 골라 그 안의 정확히 한 글자를 다른 문자로 바꾸었을 때, 그 결과가 t의 부분 문자열 중 하나와 일치하게 되는 모든 경우의 수입니다.

예시로 살펴보기

입력이 s = "sts", t = "tsts"라고 한다면 정답은 6입니다. 한 글자만 차이 나는 s와 t의 부분 문자열 쌍은 다음과 같습니다.

s[0]의 "s" ↔ t[0]의 "t"
s[0]의 "s" ↔ t[2]의 "t"
s[1]의 "t" ↔ t[1]의 "s"
s[1]의 "t" ↔ t[3]의 "s"
s[2]의 "s" ↔ t[0]의 "t"
s[2]의 "s" ↔ t[2]의 "t"

각 쌍에서 앞쪽 요소는 s에서 선택한 부분 문자열, 뒤쪽 요소는 t에서 선택한 부분 문자열입니다. 이 예시에서는 길이가 1인 부분 문자열끼리 비교했을 때 서로 다른 조합이 총 6가지 존재하므로 정답이 6이 됩니다.

풀이 접근 방법

이 문제는 모든 시작 위치의 조합을 확인하는 브루트포스 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

n1 := s의 길이
n2 := t의 길이
ans := 0
s의 모든 인덱스 i1과 문자 c1에 대해 다음을 반복합니다.
- t의 모든 인덱스 i2와 문자 c2에 대해 다음을 반복합니다.
  - i := i1, j := i2로 초기화합니다.
  - i < n1이고 j < n2이며 s[i] == t[j]인 동안 i와 j를 1씩 증가시킵니다. (일치하는 접두사 구간을 건너뜁니다)
  - 만약 i < n1이고 j < n2이면서 s[i] != t[j]라면:
    - i와 j를 1씩 증가시키고 ans를 1 증가시킵니다. (정확히 한 글자가 어긋나는 지점)
    - 그다음 i < n1이고 j < n2이며 s[i] == t[j]인 동안 i와 j를 증가시키고, 매 단계마다 ans를 1씩 증가시킵니다. (불일치 이후 일치가 이어지는 만큼 추가로 카운트)
모든 반복이 끝나면 ans를 반환합니다.

정리하면, 각 시작 위치 쌍 (i1, i2)에 대해 먼저 일치하는 구간을 건너뛴 뒤, 딱 한 글자만 어긋나는 지점을 발견하면 그 이후로 두 문자가 계속 일치하는 동안 모두 유효한 답으로 세는 방식입니다.

Python 구현 코드

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(s, t):
    n1 = len(s)
    n2 = len(t)
    ans = 0

    for i1, c1 in enumerate(s):
        for i2, c2 in enumerate(t):
            i = i1
            j = i2

            while i < n1 and j < n2 and s[i] == t[j]:
                i += 1
                j += 1

            if i < n1 and j < n2 and s[i] != t[j]:
                i += 1
                j += 1
                ans += 1
                while i < n1 and j < n2 and s[i] == t[j]:
                    i += 1
                    j += 1
                    ans += 1

    return ans

s = "sts"
t = "tsts"
print(solve(s, t))

실행 결과

입력:

"sts", "tsts"

출력:

마무리

이 알고리즘은 모든 시작 위치 조합을 탐색하므로 최악의 경우 시간 복잡도는 O(n1 × n2 × min(n1, n2))입니다. 문자열 길이가 크지 않은 문제에서는 충분히 실용적이며, 두 문자열 사이에서 정확히 한 글자만 다른 공통 부분 문자열을 세는 대표적인 패턴을 익히기에 좋은 예제입니다.