Dijkstra or Floyd Warshall and DP

This is the 4th question of the LC contest 377. It is hard especially when the time used to solve this problem is limited.

Problem

Minimum Cost to Convert String II

Solution 1 Dijkstra and DP (TLE)

const int INF = 0x3f3f3f3f;

typedef pair<int, string> PIS;
typedef long long LL;
const LL INFINF = 0x3f3f3f3f3f3f3f3f;

unordered_map<string, int> naive_dijkstra(unordered_map<string, vector<string>> &graph,  unordered_map<string, unordered_map<string, int>>&costs, string src, vector<string>& b)
{  // init distance from src to a node
    unordered_map<string, int>dis;
    for (auto &c: b){
        dis[c] = INF;
        
    }
    dis[src] = 0;
   // python syntex: dis = [float("inf")]*n
   set<PIS> pq;
   // init the unexplored nodes
   for (auto [i, v]: dis) 
   {
      if (i == src) pq.emplace(0, i);
      else pq.emplace(v, i);
   }
     
   while (!pq.empty())
   {
     // pick up the shorted node from unexplored nodes
     auto [cost, u] = *(pq.begin()); pq.erase(pq.begin());
     // explore neighbors
      
       
     for (auto &v: graph[u])
     {
        // cout << v <<endl;
        int new_cost = cost + costs[u][v];
        // find a shorter path:
        if (new_cost < dis[v])
        {
           // update
           // delete the old one
           pq.erase(pq.find({dis[v], v}));
           // update the dis[v] to the new one
           dis[v] = new_cost;
           // put the new one into the set
           pq.emplace(dis[v], v);
        }
     }
    
   }
   
    
    
    
return dis;
    }
LL min_dis[1010];
LL memo[1010];
class Solution {
public:
    LL  backtrack(int i, int m, unordered_map<char, vector<int>>&lenss, string &source, string & target, unordered_map<string, unordered_map<string, int>>&fin_dis){
       // cout << i << " "<< curr_cost << " "<<min_cost <<endl;
       if (memo[i] != -1)return memo[i];
      
        if (i == m){
            return 0;
        }
        LL ret = INFINF;
        if (target[i] ==source[i]){
            auto this_ret = backtrack(i + 1 ,m, lenss, source, target, fin_dis);
            ret = min(ret, this_ret);
        }
        for (auto len: lenss[source[i]]){
            if (i + len > m)continue;
            string s = source.substr(i, len);
            string s2 = target.substr(i, len);
            if (fin_dis.find(s) == fin_dis.end() || fin_dis[s].find(s2)==fin_dis[s].end() || fin_dis[s][s2] == INF)continue;
            auto this_ret = fin_dis[s][s2]  + backtrack(i + len ,m, lenss, source, target,fin_dis);
           ret = min(ret, this_ret);
        }
        return memo[i] = ret;
    }
    long long minimumCost(string source, string target, vector<string>& a, vector<string>& b, vector<int>& cost) {
        const int n = a.size();
        unordered_map<string, vector<string>>graph;
        unordered_map<string, unordered_map<string, int>>costs;
        string ss = "abcdefghijklmnopqrstuvwxyz";
        
       
        
        for (int i =0; i < n; ++i){
            graph[a[i]].push_back(b[i]);
            if (costs[a[i]].find(b[i]) != costs[a[i]].end()){
                costs[a[i]][b[i]] = min(costs[a[i]][b[i]], cost[i]);
            } else {
                costs[a[i]][b[i]] =  cost[i];
            }
        }
         unordered_map<string, unordered_map<string, int>>fin_dis;
        for (auto c: a){
            fin_dis[c] = naive_dijkstra(graph,costs, c, b );
        }
        
       
        const int m = source.size();
        unordered_map<char, unordered_set<int>>lens;
        for (auto c: a){
            lens[c[0]].insert(c.size());
        }
         unordered_map<char, vector<int>>lenss;
         for (auto [c, v]: lens){
             for (auto v_:v){
                 lenss[c].push_back(v_);
             }
         }
       
        
        memset(min_dis, 0x3f, sizeof min_dis);
        memset(memo, -1, sizeof memo);
        auto ret = backtrack(0,m, lenss, source, target,fin_dis);
        return ret == INFINF? -1 : ret;   
    }
};

Actually the code is OK just a bit slow as shown here:

Solution 2 Dijkstra and DP with slightly optimization (AC 1550ms)

The main optimization goes to that the a might have duplicated values, remove those duplicated values can speed up the code and get AC, however, the speed is still slow.

Key step to remove the duplication and get AC

unordered_set<string> aa(a.begin(), a.end());

The whole code

const int INF = 0x3f3f3f3f;

typedef pair<int, string> PIS;
typedef long long LL;
const LL INFINF = 0x3f3f3f3f3f3f3f3f;

unordered_map<string, int> naive_dijkstra(unordered_map<string, vector<string>> &graph,  unordered_map<string, unordered_map<string, int>>&costs, string src, vector<string>& b)
{  // init distance from src to a node
    unordered_map<string, int>dis;
    for (auto &c: b){
        dis[c] = INF;
        
    }
    dis[src] = 0;
   // python syntex: dis = [float("inf")]*n
   set<PIS> pq;
   // init the unexplored nodes
   for (auto [i, v]: dis) 
   {
      if (i == src) pq.emplace(0, i);
      else pq.emplace(v, i);
   }
     
   while (!pq.empty())
   {
     // pick up the shorted node from unexplored nodes
     auto [cost, u] = *(pq.begin()); pq.erase(pq.begin());
     // explore neighbors
      
       
     for (auto &v: graph[u])
     {
        // cout << v <<endl;
        int new_cost = cost + costs[u][v];
        // find a shorter path:
        if (new_cost < dis[v])
        {
           // update
           // delete the old one
           pq.erase(pq.find({dis[v], v}));
           // update the dis[v] to the new one
           dis[v] = new_cost;
           // put the new one into the set
           pq.emplace(dis[v], v);
        }
     }
    
   }
   
    
    
    
return dis;
    }
LL min_dis[1010];
LL memo[1010];
class Solution {
public:
    LL  backtrack(int i, int m, vector<int>&lenss, string &source, string & target, unordered_map<string, unordered_map<string, int>>&fin_dis){
       // cout << i << " "<< curr_cost << " "<<min_cost <<endl;
       if (memo[i] != -1)return memo[i];
      
        if (i == m){
            return 0;
        }
        LL ret = INFINF;
        if (target[i] ==source[i]){
            auto this_ret = backtrack(i + 1 ,m, lenss, source, target, fin_dis);
            ret = min(ret, this_ret);
        }
        for (auto len: lenss){
            if (i + len > m)continue;
            string s = source.substr(i, len);
             if (fin_dis.find(s) == fin_dis.end())continue;
            string s2 = target.substr(i, len);
            if( fin_dis[s].find(s2)==fin_dis[s].end() || fin_dis[s][s2] == INF)continue;
            auto this_ret = fin_dis[s][s2]  + backtrack(i + len ,m, lenss, source, target,fin_dis);
           ret = min(ret, this_ret);
        }
        return memo[i] = ret;
    }
    long long minimumCost(string source, string target, vector<string>& a, vector<string>& b, vector<int>& cost) {
        const int n = a.size();
        unordered_map<string, vector<string>>graph;
        unordered_map<string, unordered_map<string, int>>costs;
        string ss = "abcdefghijklmnopqrstuvwxyz";
        
       
        
        for (int i =0; i < n; ++i){
            graph[a[i]].push_back(b[i]);
            if (costs[a[i]].find(b[i]) != costs[a[i]].end()){
                costs[a[i]][b[i]] = min(costs[a[i]][b[i]], cost[i]);
            } else {
                costs[a[i]][b[i]] =  cost[i];
            }
        }
         unordered_map<string, unordered_map<string, int>>fin_dis;
          unordered_set<string> aa(a.begin(), a.end());
        for (auto c: aa){
            fin_dis[c] = naive_dijkstra(graph,costs, c, b );
        }
        
       
        const int m = source.size();
        unordered_set<int>lens;
        for (auto c: a){
            lens.insert(c.size());
        }
        vector<int>lenss(lens.begin(), lens.end());
        
        memset(min_dis, 0x3f, sizeof min_dis);
        sort(lenss.begin(), lenss.end());
        reverse(lenss.begin(), lenss.end());
        memset(memo, -1, sizeof memo);
        auto ret = backtrack(0,m, lenss, source, target,fin_dis);
        return ret == INFINF? -1 : ret;   
    }
};

Solution 3 Dijkstra and DP with further optimization (AC 946 ms)

The solution 1 and solution 2 areslow, which might be caused using string as the key is slow, what if we use the index of the string instead of the string itself as the key?

const int INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef long long LL;
const LL INFINF = 0x3f3f3f3f3f3f3f3f;
LL min_dis[1010];
LL memo[1010];
int costs[210][210];
int fin_dis[210][210];
void naive_dijkstra(int src, int m,  vector<vector<int>> &graph)
{  // init distance from src to a node
    vector<int>dis(m, INF);
    dis[src] = 0;

   
   set<PII> pq;
   // init the unexplored nodes
   for (int j = 0; j < m; ++j) 
   {
      pq.emplace(dis[j], j);
   }
     
   while (!pq.empty())
   {
     // pick up the shorted node from unexplored nodes
     auto [cost, u] = *(pq.begin()); pq.erase(pq.begin());
     // explore neighbors
      
       
     for (auto &v: graph[u])
     {
        // cout << v <<endl;
        int new_cost = cost + costs[u][v];
        // find a shorter path:
        if (new_cost < dis[v])
        {
           // update
           // delete the old one
           pq.erase(pq.find({dis[v], v}));
           // update the dis[v] to the new one
           dis[v] = new_cost;
           // put the new one into the set
           pq.emplace(dis[v], v);
        }
     }
    
   }
    for (int j = 0; j < m; ++j){
        fin_dis[src][j] = dis[j];
    }
    return;
    }

class Solution {
public:
    LL  backtrack(int i, int m, unordered_map<char, vector<int>>&lenss, string &source, string & target, unordered_map<string, int>& s_idx ){
       // cout << i << " "<< curr_cost << " "<<min_cost <<endl;
       if (memo[i] != -1)return memo[i];
      
        if (i == m){
            return 0;
        }
        LL ret = INFINF;
        if (target[i] ==source[i]){
            auto this_ret = backtrack(i + 1 ,m, lenss, source, target, s_idx);
            ret = min(ret, this_ret);
        }
        for (auto len: lenss[source[i]]){
            if (i + len > m)continue;
            string s = source.substr(i, len);
            string s2 = target.substr(i, len);
            if (s_idx.find(s) == s_idx.end() || s_idx.find(s2) == s_idx.end())continue;
            int u = s_idx[s], v = s_idx[s2];
            if (fin_dis[u][v] == INF)continue;
            auto this_ret = fin_dis[u][v]  + backtrack(i + len ,m, lenss, source, target,s_idx);
           ret = min(ret, this_ret);
        }
        return memo[i] = ret;
    }
    long long minimumCost(string source, string target, vector<string>& a, vector<string>& b, vector<int>& cost) {
        const int n = a.size();
       
        memset(costs, 0x3f, sizeof costs);
        
      
       
        unordered_set<string> nodes;
        unordered_map<string, unordered_map<string, int>> temp_costs;
        unordered_map<string, unordered_map<string, int>> min_cost_idx;
        vector<int> to_be_removed_idxes;
         unordered_map<string, int> s_idx;
        for (int i =0; i < n; ++i){
            string s1 = a[i], s2 = b[i];
            
            if (s_idx.find(s1) == s_idx.end()){      
                s_idx[s1] = s_idx.size();
            }
             if (s_idx.find(s2) == s_idx.end()){      
                s_idx[s2] = s_idx.size();
            }
            int u =  s_idx[s1] , v =  s_idx[s2];
            if (temp_costs[a[i]].find(b[i]) != temp_costs[a[i]].end()){
                if (cost[i] < temp_costs[a[i]][b[i]]){
                    temp_costs[a[i]][b[i]] = cost[i];
                    to_be_removed_idxes.push_back(min_cost_idx[a[i]][b[i]]);
                    min_cost_idx[a[i]][b[i]] = i;
                } else {
                     to_be_removed_idxes.push_back(i);
                }
               
            } else {
                temp_costs[a[i]][b[i]] = cost[i];
                min_cost_idx[a[i]][b[i]] = i;
            }
        }
        sort(to_be_removed_idxes.begin(), to_be_removed_idxes.end());
        int idx = 0;
        const int m = s_idx.size();
        vector<vector<int>>graph(m);
        for (int i = 0; i < n; ++i){
            if (idx < to_be_removed_idxes.size() && i == to_be_removed_idxes[idx]){
                idx++;
                continue;
            }
            string s1 = a[i], s2 = b[i];
            int u = s_idx[s1], v = s_idx[s2];
            graph[u].push_back(v);
            costs[u][v] = cost[i];
        }
        memset(fin_dis, 0x3f, sizeof fin_dis);
        for (int i = 0; i < m; ++i){
            naive_dijkstra(i, m, graph);
        }
        
       
        const int sz_source = source.size();
        unordered_map<char, unordered_set<int>>lens;
        for (auto c: a){
            lens[c[0]].insert(c.size());
        }
         unordered_map<char, vector<int>>lenss;
         for (auto [c, v]: lens){
             for (auto v_:v){
                 lenss[c].push_back(v_);
             }
         }
       
        
        memset(min_dis, 0x3f, sizeof min_dis);
        memset(memo, -1, sizeof memo);
        auto ret = backtrack(0,sz_source, lenss, source, target, s_idx);
        return ret == INFINF? -1 : ret;   
    }
};

Solution 4 Floyd Warshall and DP (AC 764 ms)

Based on solution3, we can replace the Dijkstra to Floyd Warshall as we most have 200 nodes. O(n³) is doable.

const int INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef long long LL;
const LL INFINF = 0x3f3f3f3f3f3f3f3f;
LL min_dis[1010];
LL memo[1010];
int costs[210][210];
int fin_dis[210][210];
void floyd_warshall(int m,  vector<vector<int>> &graph)
{  for (int i = 0; i < m; ++i){
    for (int j = 0; j < m; ++j){
        if (costs[i][j] == INF)continue;
        fin_dis[i][j] = costs[i][j];
    }
}
    for (int i = 0; i < m; ++i)fin_dis[i][i] = 0;
    for (int k = 0; k < m; ++k)
    for (int i = 0; i < m; ++i)
    for (int j = 0; j < m; ++j)
        fin_dis[i][j] = min(fin_dis[i][j], fin_dis[i][k]+fin_dis[k][j]);
}

class Solution {
public:
    LL  backtrack(int i, int m, unordered_map<char, vector<int>>&lenss, string &source, string & target, unordered_map<string, int>& s_idx ){
       // cout << i << " "<< curr_cost << " "<<min_cost <<endl;
       if (memo[i] != -1)return memo[i];
      
        if (i == m){
            return 0;
        }
        LL ret = INFINF;
        if (target[i] ==source[i]){
            auto this_ret = backtrack(i + 1 ,m, lenss, source, target, s_idx);
            ret = min(ret, this_ret);
        }
        for (auto len: lenss[source[i]]){
            if (i + len > m)continue;
            string s = source.substr(i, len);
            string s2 = target.substr(i, len);
            if (s_idx.find(s) == s_idx.end() || s_idx.find(s2) == s_idx.end())continue;
            int u = s_idx[s], v = s_idx[s2];
            if (fin_dis[u][v] == INF)continue;
            auto this_ret = fin_dis[u][v]  + backtrack(i + len ,m, lenss, source, target,s_idx);
           ret = min(ret, this_ret);
        }
        return memo[i] = ret;
    }
    long long minimumCost(string source, string target, vector<string>& a, vector<string>& b, vector<int>& cost) {
        const int n = a.size();
       
        memset(costs, 0x3f, sizeof costs);
        
      
       
        unordered_set<string> nodes;
        unordered_map<string, unordered_map<string, int>> temp_costs;
        unordered_map<string, unordered_map<string, int>> min_cost_idx;
        vector<int> to_be_removed_idxes;
         unordered_map<string, int> s_idx;
        for (int i =0; i < n; ++i){
            string s1 = a[i], s2 = b[i];
            
            if (s_idx.find(s1) == s_idx.end()){      
                s_idx[s1] = s_idx.size();
            }
             if (s_idx.find(s2) == s_idx.end()){      
                s_idx[s2] = s_idx.size();
            }
            int u =  s_idx[s1] , v =  s_idx[s2];
            if (temp_costs[a[i]].find(b[i]) != temp_costs[a[i]].end()){
                if (cost[i] < temp_costs[a[i]][b[i]]){
                    temp_costs[a[i]][b[i]] = cost[i];
                    to_be_removed_idxes.push_back(min_cost_idx[a[i]][b[i]]);
                    min_cost_idx[a[i]][b[i]] = i;
                } else {
                     to_be_removed_idxes.push_back(i);
                }
               
            } else {
                temp_costs[a[i]][b[i]] = cost[i];
                min_cost_idx[a[i]][b[i]] = i;
            }
        }
        sort(to_be_removed_idxes.begin(), to_be_removed_idxes.end());
        int idx = 0;
        const int m = s_idx.size();
        vector<vector<int>>graph(m);
        for (int i = 0; i < n; ++i){
            if (idx < to_be_removed_idxes.size() && i == to_be_removed_idxes[idx]){
                idx++;
                continue;
            }
            string s1 = a[i], s2 = b[i];
            int u = s_idx[s1], v = s_idx[s2];
            graph[u].push_back(v);
            costs[u][v] = cost[i];
        }
        memset(fin_dis, 0x3f, sizeof fin_dis);
        floyd_warshall(m, graph);
    
        const int sz_source = source.size();
        unordered_map<char, unordered_set<int>>lens;
        for (auto c: a){
            lens[c[0]].insert(c.size());
        }
         unordered_map<char, vector<int>>lenss;
         for (auto [c, v]: lens){
             for (auto v_:v){
                 lenss[c].push_back(v_);
             }
         }

        
        memset(min_dis, 0x3f, sizeof min_dis);
        memset(memo, -1, sizeof memo);
        auto ret = backtrack(0,sz_source, lenss, source, target, s_idx);
        return ret == INFINF? -1 : ret;   
    }
};

Take away

• Floyd Warshall can be used when node size is small such as < 200
• Using string to build graph is much slower. Thinking about using the index of string instead.

Solution 4 in python

Similar idea of solution 4 in Python. Code is much shorter, however, the running time is long.

INF = float("inf")
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        n = len(source)
        nodes = {node:i  for i, node in enumerate(set(original + changed))}
        graph = collections.defaultdict(list)
        m = len(nodes)
        dis = [[INF]*m for _ in range(m)]
        for i in range(m):
            dis[i][i] = 0
        for u, v, c in zip(original, changed, cost):
            graph[u].append(v)
            i, j = nodes[u], nodes[v]
            dis[i][j] = min(dis[i][j], c)
        for node in graph.keys():
            graph[node] = list(set(graph[node]))
        def folyd():
            for k in range(m):
                for i in range(m):
                    for j in range(m):
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        folyd()
        lens = {len(s) for s in original}
        @lru_cache(None)
        def dp(i):
            if i == n:
                return 0
            ret = INF
            if source[i] == target[i]:
                ret = min(ret, dp(i+1))
            for l in lens:
                if i + l > n:
                    continue
                s1,s2 = source[i: i +l], target[i: i +l]
                if s1 not in nodes or s2 not in nodes:
                    continue
                u_idx, v_idx = nodes[s1], nodes[s2]
                if  dis[u_idx][v_idx] == INF:
                    continue
                this_ret = dis[u_idx][v_idx] + dp(i + l)
                ret = min(ret, this_ret)
            return ret
        ret = dp(0)
        return -1 if ret == INF else ret