1. 문제 소개

2976. Minimum Cost to Convert String I

2. 풀이

시간복잡도는 $O(26^3 + |\text{source}|)$이다.

class Solution:                                                                 # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def minimumCost(self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]) -> int:  # 최소 변환 비용을 반환하는 함수
        inf = float('inf')                                                      # 도달 불가능을 표현할 무한대 값을 설정
        dist = [[inf] * 26 for _ in range(26)]                                  # 26×26 최단비용 행렬을 inf로 초기화

        for i in range(26):                                                     # 모든 문자 i에 대해
            dist[i][i] = 0                                                      # 자기 자신으로의 변환 비용은 0으로 설정

        for o, c, z in zip(original, changed, cost):                             # 주어진 직접 변환 규칙들을 순회하며
            u = ord(o) - 97                                                     # 시작 문자를 0..25 인덱스로 변환
            v = ord(c) - 97                                                     # 도착 문자를 0..25 인덱스로 변환
            dist[u][v] = min(dist[u][v], z)                                     # 동일 변환이 여러 번 주어지면 최소 비용만 유지

        for k in range(26):                                                     # Floyd-Warshall의 중간 노드 k를 순회
            for i in range(26):                                                 # 시작 노드 i를 순회
                if dist[i][k] == inf:                                           # i->k가 불가능하면
                    continue                                                    # k를 거치는 경로는 의미 없으므로 건너뜀
                for j in range(26):                                             # 도착 노드 j를 순회
                    if dist[k][j] != inf:                                       # k->j가 가능하면
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])   # i->k->j 경로로 최단비용을 완화

        total_cost = 0                                                          # 전체 변환 비용 누적 변수를 0으로 초기화
        for s_char, t_char in zip(source, target):                              # source와 target을 같은 위치끼리 순회
            u = ord(s_char) - 97                                                # source 문자를 인덱스로 변환
            v = ord(t_char) - 97                                                # target 문자를 인덱스로 변환
            if u == v:                                                          # 이미 같은 문자면
                continue                                                        # 변환 비용이 0이므로 건너뜀
            if dist[u][v] == inf:                                               # u->v 변환이 불가능하면
                return -1                                                       # 전체 변환이 불가능하므로 -1 반환
            total_cost += dist[u][v]                                            # 해당 위치의 최소 변환 비용을 누적

        return total_cost                                                       # 누적된 최소 총 비용을 반환

3. 마무리

혼자 힘으로 풀지 못해 아쉽다.