[LeetCode] 2976. Minimum Cost to Convert String I

https://leetcode.com/problems/minimum-cost-to-convert-string-i/description/?envType=daily-question&envId=2024-07-27

leetcode - Minimum Cost to Convert String I

문제 유형 : 문자열 처리, 최단거리, bfs

문제 난이도 : Medium

 

문제

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

 

0-indexed의 길이가 같은 문자열 source와 target이 주어진다. 모두 영어 소문자이다.

0-indexed의 길이가 같은 배열 original, changed, cost가 주어진다. 글자 original[i]를 changed[i]로 바꾸는 데 cost비용이 든다.

 

source를 target으로 변환하기 위한 최소비용을 구하시오.

불가능하면 -1을 반환하시오.

 

original이랑 changed에서 중복이 있을 수 있습니다.

 

풀이

source, target, cost를 이용하여 가중치가 있는 방향그래프를 만들 수 있다.

그래프를 만들고, 26 * 26의 2D 배열을 만들어서 costs[i][j] = i부터 j까지 가는데 드는 최소 비용으로 한다.

 

각각의 알파벳에 대해 그래프 출발점으로 하고, 다익스트라를 이용하여 비용 테이블을 채운다.

source와 target의 글자를 하나씩 읽어서 costs[src][dst]가 닿을 수 없다면 -1을 반환하고, 아니라면 costs[src][dst]를 각각 누적시켜서 반환한다.

 

 

코드

C++

#pragma GCC optimize("03". "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        int n = cost.size();
        int m = source.size();
        vector<vector<pair<int, int>>> graph(26);
        vector<vector<int>> costs(26, vector<int>(26, INT_MAX));
        for(int i = 0; i < n; i++) {
            int src = original[i] - 'a';
            int dst = changed[i] - 'a';
            int costToChange = cost[i];

            graph[src].push_back({dst, costToChange});
        }

        for(int i = 0; i < 26; i++) {
            queue<int> q;
            q.push(i);
            costs[i][i] = 0;

            while(!q.empty()) {
                int curr = q.front();
                q.pop();

                for(const auto &next : graph[curr]) {
                    int nextLetter = next.first;
                    int nextCost = next.second;

                    if(costs[i][curr] + nextCost < costs[i][nextLetter]) {
                        q.push(nextLetter);
                        costs[i][nextLetter] = costs[i][curr] + nextCost;
                    }
                }
            }
        }

        long long ans = 0;
        for(int i = 0; i < m; i++) {
            int src = source[i] - 'a';
            int dst = target[i] - 'a';
            if(costs[src][dst] == INT_MAX) return -1;
            ans += costs[src][dst];
        }

        return ans;
    }
};