Lintcode 1411. Edit Distance - Replace Edition

Given two strings s1 and s2, find the least number of operations and make the two strings equal.
In this problem, an operation is defined as replace one kind of character to another character indefinitely.

Example

Example 1:

Input: s1 = "abb", s2 = "dad"
Output: 2
Explantion: Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.

Notice

Two strings with same length consisting only of lowercase English letters.

Solution:

Use Union Find. For each character from s1 to s2, say c1->c2, if there is a change, we connect c1 to c2 in one connected component. 

Code (Java):

public class Solution {
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: the least number of operations and make the two strings equal
     */
    public int editDistance(String s1, String s2) {
        // Write your code here
        if (s1 == null || s1.length() == 0) {
            return 0;
        }
        
        int[] parents = new int[26];
        int ans = 0;
        
        for (int i = 0; i < 26; i++) {
            parents[i] = i;
        }
        
        for (int i = 0; i < s1.length(); i++) {
            int n1 = s1.charAt(i) - 'a';
            int n2 = s2.charAt(i) - 'a';
            
            int p1 = find(n1, parents);
            int p2 = find(n2, parents);
            
            if (p1 != p2) {
                ans++;
                parents[p1] = p2;
            }
        }
        
        return ans;
    }
    
    private int find(int node, int[] parents) {
        int root = node;
        
        while (parents[root] != root) {
            root = parents[root];
        }
        
        while (root != node) {
            int parent = parents[node];
            parents[node] = root;
            node = parent;
        }
        
        return root;
    }
}