2976 - Minimum Cost to Convert String I

 JAVA

• class Solution {
      public long minimumCost(
          String source, String target, char[] original, char[] changed, int[] cost) {
          final int inf = 1 << 29;
          int[][] g = new int[26][26];
          for (int i = 0; i < 26; ++i) {
              Arrays.fill(g[i], inf);
              g[i][i] = 0;
          }
          for (int i = 0; i < original.length; ++i) {
              int x = original[i] - 'a';
              int y = changed[i] - 'a';
              int z = cost[i];
              g[x][y] = Math.min(g[x][y], z);
          }
          for (int k = 0; k < 26; ++k) {
              for (int i = 0; i < 26; ++i) {
                  for (int j = 0; j < 26; ++j) {
                      g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                  }
              }
          }
          long ans = 0;
          int n = source.length();
          for (int i = 0; i < n; ++i) {
              int x = source.charAt(i) - 'a';
              int y = target.charAt(i) - 'a';
              if (x != y) {
                  if (g[x][y] >= inf) {
                      return -1;
                  }
                  ans += g[x][y];
              }
          }
          return ans;
      }
  }

C++

• class Solution {
  public:
      long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
          const int inf = 1 << 29;
          int g[26][26];
          for (int i = 0; i < 26; ++i) {
              fill(begin(g[i]), end(g[i]), inf);
              g[i][i] = 0;
          }
  
          for (int i = 0; i < original.size(); ++i) {
              int x = original[i] - 'a';
              int y = changed[i] - 'a';
              int z = cost[i];
              g[x][y] = min(g[x][y], z);
          }
  
          for (int k = 0; k < 26; ++k) {
              for (int i = 0; i < 26; ++i) {
                  for (int j = 0; j < 26; ++j) {
                      g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                  }
              }
          }
  
          long long ans = 0;
          int n = source.length();
          for (int i = 0; i < n; ++i) {
              int x = source[i] - 'a';
              int y = target[i] - 'a';
              if (x != y) {
                  if (g[x][y] >= inf) {
                      return -1;
                  }
                  ans += g[x][y];
              }
          }
          return ans;
      }
  };