Leetcode: String Transforms Into Another String

This question is asked at Bytedance and Google. Given 2 strings str1 and str2 of the same length determine wheter you can transform str1 into str2 by doing zero or more conversions. 

In one conversion, you can convert all the occurances of one characters to any lowercase english character. Return  true if and only if you can transform str1 to str2. Here are the examples:

Example 1:

"aabcc"  -----> 

"aabee" -------->

"aadee" ----->

"ccdee"

Here are the hints: 

1. Model the graph as a graph problem, add an edge from one character to another if you need to convert them. 

2. If a character needs to be converted into more than one character, there would be no solution. This means that every node can have at least one outgoing edge.

Modelling this is a graph would be the most intuitive way. We realize that the out degree of a node has to be smaller or equal to 1 otherwise we return false immediately. We should use a hashmap and a linkedlist to keep track of the edges accordingly. 

"et" can transform into "te", so a cycle is definitely possible. We use the hashmap to figure out if the keys are already used. We want to see if the size of the set is less than 26 so we will have less than 26 one to one mappings. You can't change 26 characters without it becoming an overlap situation. Here's the final code: 

class Solution {

    public boolean canConvert(String str1, String str2) {

        //base case, we don't even have to change anything. 

        if (str1.equals(str2)) {

            return true;

        }

        Map<Character, Character> map = new HashMap<>();

        for (int i = 0; i < str1.length(); i++) {

            //point the characters in the hashmap

            char c1 = str1.charAt(i);

            char c2 = str2.charAt(i);

            //if the map contains the character already and more than one outward edge, return false.

           if (map.containsKey(c1) && map.get(c1) != c2) {

                return false;

            }

            //else put the connection to the map

            map.put(c1, c2);

        }

        //see if the new hashset has less than 26 connections, otherwise there will be an issue with unique characters once you change one. 

        return new HashSet<Character>(map.values()).size() < 26;

    }

}