Leetcode 1153: String Transforms Into Another String

https://leetcode.com/contest/biweekly-contest-6/problems/string-transforms-into-another-string/

Note:

1. 1 <= str1.length == str2.length <= 10^4
2. Both str1 and str2 contain only lowercase English letters

Notes:

This question looks like not as hard as labeled, but actually its logic is not easy.

1): When str1 == str2, it is always true;

2): One of the key observation is that: when the same letter at different positions in str1 corresponds to different letters in str2 , there is no way to match them. Thus we can return false directly. We can use an hash table to record the relationships between str1 and str2. This is an important conclusion, but is not the main problem to this question.

3): The main problem is the situations when there are "loops". For example, str1 = "ab", and str2 = "ba". So there is a loop as 'a' -> 'b' -> 'a' . In this case, we need to break the loop. For example, we can set 'a' in str1 = 'c' firstly because there is no 'c' in str2. After the setting, the relationship becomes 'c' -> 'b' -> 'a'. Or the "loop" becomes a "linked list". Then we can start to set 'b' = 'a' ; then set 'c' = 'b'. Done. It is interesting that we cannot start with setting 'c' in str1 to 'b'. Then it will become "bb" to ''ba", which cannot be matched based on 2). So we need to start from the end of the "linked list" for the match.

3): So the second observation is that, when there is a "loop", we need to break the "loop" to a "linked list" by using a "missing" letter in str2; then we can start the match from the end of the "linked list", or we can always start with the positions where the letters in str2 that does not show up in str1. For example, the above Example 1: we start either i = 2 or 3, but we cannot start with i = 0.

4): Now is the key: after finishing the scan of the str1 and str2, we do not reach a false. In this situation, the maximum number of hash.size() is 26. Why? because there are 26 kinds of letters in total, and based on 2) one letter can only correspond to one letter. If the size of the hash table is 26, it means there are 26 kinds of letters in str1 and there are at most 26 kinds of letters in str2. Since we do not reach a false: there are only two situations left: (a): str1 == st2, which is case 1) and is always true; (b) there are "linked lists" or "loops". For the former, we can always match them, as described in 3). If a loop exists, we need a "missing" letter in str2 to break the loop. But if there is no "missing" letter in str2, or the total kinds of letter in str2 is 26, then it should return false; otherwise, there are always some "missing" letters to break the loops if exist, then it becomes "linked lists" which can always be matched.

In addition, let us look at another example: str1 = "ab", and str2 = "bb". In this case, only short "linked list" existing: 'a' -> 'b'. So we just need to set 'a' to 'b'. Done. So for such one step short lists, we can always match them. So the third observation, when all the letters in str2 that can be found in str1 have been matched, we can continue the match with positions where the letters in str1 that does not show up in str2. (After this is done, it either is finished or only loops left. For the case there are loops, we need to break the loops first.)


See the code below,

class Solution {
public:
    bool canConvert(string str1, string str2) {
        if(str1 == str2) return true;//cannot be deleted. corner case: both contain a-z.
        unordered_map<char, char> ump;//record relationships
        set<char> cts;//count kinds of letters in str2
        for(int i=0; i<str1.size(); ++i) {
            int a = str1[i], b = str2[i];
            if(ump.count(a) && ump[a] != b) return false;
            ump[a] = b;
            cts.insert(b);
        }
        return cts.size() < 26;
    }
};

Follow up: if it is true, what are the minimum steps to finish the conversion?