Leetcode 3302. Find the Lexicographically Smallest Valid Sequence

문제

You are given two strings word1 and word2.

A string x is called almost equal to y if you can change at most one character in x to make it identical to y.

A sequence of indices seq is called valid if:

The indices are sorted in ascending order.
Concatenating the characters at these indices in word1 in the same order results in a string that is almost equal to word2.
Return an array of size word2.length representing the lexicographically smallest valid sequence of indices. If no such sequence of indices exists, return an empty array.

Note that the answer must represent the lexicographically smallest array, not the corresponding string formed by those indices.

문자열 word1과 word2가 주어집니다.

문자열 x의 최대 한 글자만 변경해서 y와 완전히 동일하게 만들 수 있다면, x와 y는 거의 같다(almost equal)고 합니다.

인덱스들의 수열 seq가 다음 조건을 만족하면 유효한 수열(valid sequence)이라고 합니다.

1. 인덱스들은 오름차순으로 정렬되어 있어야 합니다.
2. word1에서 seq에 포함된 인덱스의 문자들을 순서대로 이어 붙였을 때 만들어지는 문자열이 word2와 거의 같아야 합니다.

word2.length 크기의 유효한 인덱스 수열 중에서 사전순으로 가장 작은 수열을 반환하세요.

만약 유효한 인덱스 수열이 존재하지 않는다면 빈 배열 []을 반환하세요.

주의:
사전순으로 가장 작아야 하는 것은 선택된 문자들로 만들어진 문자열이 아니라, 인덱스 배열 자체입니다.

---

예시

입력: word1 = "vbcca", word2 = "abc"

출력: [0,1,2]

설명:

사전순으로 가장 작은 유효한 인덱스 수열은 [0, 1, 2]입니다.

• word1[0]의 문자 'v'를 'a'로 변경합니다.
• word1[1]의 문자 'b'는 이미 일치합니다.
• word1[2]의 문자 'c'도 이미 일치합니다.

따라서 인덱스 [0,1,2]에서 뽑은 문자열은 "vbc"이고, 여기서 한 글자만 바꾸면 "abc"가 되므로 유효합니다.

---

제한

• $1 <= word2.length < word1.length <= 3 * 10^5$
• word1과 word2는 영어 소문자로만 구성된다.

---

풀이

먼저 코드를 보면 다음과 같다.

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        W1, W2 = len(word1), len(word2)
        last = [-1] * W2

        i2 = W2 - 1
        for i1 in range(W1 - 1, -1, -1):
            if word1[i1] == word2[i2]:
                last[i2] = i1
                i2 -= 1
                if i2 == -1:
                    break

        fixed = False
        ans = []
        i2 = 0

        for i1 in range(W1):
            if word1[i1] == word2[i2]:
                ans.append(i1)
                i2 += 1
            elif not fixed and (i2 == W2 - 1 or last[i2 + 1] > i1):
                fixed = True
                ans.append(i1)
                i2 += 1

            if i2 == W2:
                break

        return ans if len(ans) == W2 else []

핵심은 현재 위치에서 서로 다른 문자를 하나 선택해도, 그 뒤의 word2를 정상적으로 완성할 수 있는지 빠르게 판단하는 것이다.

이를 위해 먼저 last 배열을 만든다.

last = [-1] * W2

i2 = W2 - 1
for i1 in range(W1 - 1, -1, -1):
    if word1[i1] == word2[i2]:
        last[i2] = i1
        i2 -= 1

        if i2 == -1:
            break

word1과 word2를 뒤에서부터 비교하면서, word2를 word1의 부분 수열로 만들 수 있는 위치를 최대한 뒤쪽에서 잡는다.

따라서 last[i]는 word2[i:]를 word1에서 부분 수열로 만들 때, word2[i]를 배치할 수 있는 가장 뒤쪽의 위치라고 볼 수 있다.

예를 들어 last[i + 1] > x라면, 현재 word1[x]를 사용한 뒤에도 word2[i + 1:]를 전부 정상적으로 이어 붙일 수 있다는 뜻이다.

이 정보를 이용해 앞에서부터 사전순으로 가장 작은 인덱스들을 선택한다.

fixed = False
ans = []
i2 = 0

for i1 in range(W1):
    if word1[i1] == word2[i2]:
        ans.append(i1)
        i2 += 1

    elif not fixed and (i2 == W2 - 1 or last[i2 + 1] > i1):
        fixed = True
        ans.append(i1)
        i2 += 1

    if i2 == W2:
        break

여기서

• i1은 현재 확인하고 있는 word1의 인덱스
• i2는 현재 만들어야 하는 word2의 인덱스
• fixed는 이미 한 번의 문자 변경 기회를 사용했는지를 의미한다.

word1을 왼쪽부터 확인하면서 다음과 같이 처리한다.

1. 현재 문자가 같은 경우

if word1[i1] == word2[i2]:
    ans.append(i1)
    i2 += 1

현재 문자가 같다면 바로 선택한다.

우리가 원하는 것은 문자열 자체가 아니라 인덱스 배열의 사전순 최소값이다.

따라서 같은 문자를 사용할 수 있다면 현재의 가장 작은 i1을 즉시 선택하는 것이 항상 유리하다. 더 뒤의 같은 문자를 기다릴 이유가 없다.

---

2. 현재 문자가 다른 경우

문자가 다르더라도 문제에서는 최대 한 글자를 변경할 수 있으므로, 아직 변경 기회를 사용하지 않았다면 현재 인덱스를 선택할 수도 있다.

다만 아무 위치에서나 변경 기회를 사용하면 안 된다.

elif not fixed and (i2 == W2 - 1 or last[i2 + 1] > i1):

두 조건을 확인한다.

마지막 문자라면

i2 == W2 - 1

현재가 word2의 마지막 문자라면 이후에 맞춰야 할 문자가 없다.

따라서 아직 변경 기회를 사용하지 않았다면 현재 word1[i1]을 선택하고 그 문자를 변경하면 바로 수열을 완성할 수 있다.

뒤의 문자열을 여전히 만들 수 있다면

last[i2 + 1] > i1

현재 word1[i1]을 word2[i2]로 변경해서 사용한다고 생각해 보자.

그러면 이후에는 반드시 i1보다 큰 인덱스만 사용할 수 있다.

따라서 남은

word2[i2 + 1:]

를 word1[i1 + 1:]에서 정상적으로 만들 수 있어야 한다.

last[i2 + 1] > i1이라는 것은 뒤에서부터 최대한 늦게 배치했을 때조차 다음 문자의 위치가 현재 i1보다 뒤에 있다는 뜻이므로, 남은 문자열 전체를 현재 위치 이후에서 만들 수 있다는 것이 보장된다.

따라서 이 경우에는 현재 인덱스를 선택해도 안전하다.

fixed = True
ans.append(i1)
i2 += 1

이때 한 번의 문자 변경 기회를 사용했으므로 fixed = True로 변경한다.

왜 사전순으로 가장 작은가?

word1의 인덱스를

0 → 1 → 2 → ...

순서대로 확인하면서, 현재 인덱스를 선택해도 최종 답을 완성할 수 있는 순간 바로 선택하고 있다.

즉 각 word2[i]에 대해 가능한 가장 작은 word1의 인덱스를 선택한다.

• 문자가 같다면 바로 선택한다.
• 문자가 다르다면, 한 번의 변경으로 처리할 수 있으면서 남은 문자열까지 완성 가능한 경우에만 바로 선택한다.

따라서 앞쪽 인덱스를 불필요하게 건너뛰는 일이 없고, 결과적으로 만들어지는 ans가 사전순으로 가장 작은 유효한 인덱스 배열이 된다.

마지막으로 모든 word2의 문자를 선택했는지 확인한다.

return ans if len(ans) == W2 else []

길이가 W2보다 작다면 끝까지 유효한 수열을 만들지 못한 것이므로 빈 배열을 반환한다.

복잡도

last 배열을 만드는 과정에서 word1을 한 번 뒤에서부터 순회하고, 답을 만드는 과정에서 다시 한 번 앞에서부터 순회한다.

따라서

• 시간 복잡도: O(word1.length)
• 공간 복잡도: O(word2.length)

이다.