**To save some time ,you can directly look at the pictures and the final part.**\nThis article is really long, If you are interested in it and patient enough, you can see how I consider about this problem. You can see how I went astray and how I realizes I can optimized after I did a detailed summary. If you see others\' code, they will tell you try to cut off the circle in this question. But for beginners like me, sometimes this question can be confusing. Especially under the circumstance that I have already completed some questions on Leetcode. When I see a problem similar to my previous solved ones, I tend to feel delighted then begin to code without enough considerations. That\'s really a bad habbit for those who are going to participate in one interview. I hope this article can help you more than just solving it.\n**Feel free to leave comments if you think it\'s not good enough. Would you like to give me one thumb up?**\nI will divide this problem into three steps.\n**STEP 1:** Traverse these two strings and record which characters requiring being converted. During this period if we find some contradictory situation like "aa" to "bc", we can directly return false. The conversion must be a one-to-one relation.\n**STEP 2:** Look back at the description. We can find the order to convert each character is vital. Here are three regulations. Don\'t hurry, I will explain how I get them later with illustrations. \n1.If there is one character never occurring in the str1, we can directly return true.\n2.If there is at least one loop in the graph, don\'t panic. We still have opportunities if we cope with those nodes who are not in loop first. And we need to find some nodes as transfer stations. We need to know how many nodes are in one loop.\n3.Those characters who needn\'t a conversion are very special. They can\'t be used as transfer station. For example, as for \u201Cabcd\u201D and \u201Dabce\u201D a,b and c don\u2019t\u2019 need operations.\n**STEP 3:** Now we will make judgements based on what we have calculated. I will show you four different conditions and attempt to summarize the essence of this problem.\nBefore we go through this process, I need to introduce you my concept **\u201Ctransfer station\u201D**. Now we want to convert \u201Cac\u201D to \u201Dca\u201D. We can\u2019t directly convert a to c. We need convert a to b, then c to a, finally b to c. At here we call transfer station. We need to convert one character to one intermediate one which has no connections with other complicated part. This node is considered as transfer station. \n![image](https://assets.leetcode.com/users/images/0f1c807b-e1a8-4160-bd1a-ffe1992febb1_1597383507.1481102.png)\n\nWe can find only white nodes can be used as transfer stations after a series of operations. Now we can see the essence of this problem is whether we can find one transfer station. **So as long as we can find one transfer station, we can return true.**\n \n\n```\nclass Solution {\n //@para visited represent which characters occurred in the string\n //@para map records all the conversion relation\n Map map=new HashMap<>();\n int []visited=new int[26];\n public boolean canConvert(String str1, String str2) {\n for(int i=0;i<=25;i++)\n visited[i]=0;\n int p=0;\n //---------step1 :build the single direction graph----//\n while(p<=str1.length()-1)\n {\n visited[str1.charAt(p)-\'a\']=1;\n if(str1.charAt(p)==(str2.charAt(p)))\n p++;\n else\n {\n if(map.containsKey(str1.charAt(p)))\n {\n if(map.get(str1.charAt(p)).equals(str2.charAt(p)))\n p++;\n else \n //must be one to one relation\n //otherwise return false directly\n return false;\n }\n else\n {\n map.put(str1.charAt(p),str2.charAt(p));\n p++;\n }\n }\n }\n //-----------------------step 2 check the loop----------//\n //-----2.1 char never occurred before can be used as transfer station-------------//\n int cnt=0;\n for(int i=0;i<=25;i++)\n cnt+=visited[i];\n if(cnt<=25)\n return true;\n //---------------2.2 check how many loop and size of each loop----//\n //@para visited is cleared here, to show a node isVisited or not\n //@para total_size : the total number of nodes in loop\n //@para loop : how many loops are in the graph\n //may be you can make optimizations here, using slow and fast pointers.\n //Floyd tortoise and hare algorithm.\n for(int i=0;i<=25;i++)\n visited[i]=0;\n int total_size=0;\n int loop=0;\n for(char c:map.keySet())\n {\n if(visited[c-\'a\']==1)\n continue;\n char pre=c;\n visited[c-\'a\']=1;\n int flag=0;\n while(map.containsKey(map.get(c)))\n {\n c=map.get(c);\n if(visited[c-\'a\']==1)\n {\n flag=1;\n break;\n }\n visited[c-\'a\']=1;\n }\n //when finding one loop, we assign 1 to flag and begin to caculate the size of the loop\n if(flag==1)\n {\n loop++;\n int size=0;\n char ori=c;\n while(map.containsKey(map.get(c)))\n {\n c=map.get(c);\n size++;\n if(c==ori)\n break;\n }\n total_size+=size;\n }\n visited[pre-\'a\']=0;\n }\n //--------------step 3--------------//\n if(loop==0)\n return true;\n else if(total_size==26)\n return false;\n else if(total_size<26)\n {\n if(map.size()>total_size)\n return true;\n else\n return false;\n }\n return total_size==0;\n }\n}\n```\n**After I completed this article, I suddenly realized what I did is not wise. Check whether there is one loop and the loop size is not necessary. Floyd Tortoise and Hare does well in cope with the loop in graph, especially the graph is implemented by a linked list. Nut here we can use map and set, call the size() function then easily judge whether there is one loop.**\n\nHere map records the relation. Set1 records all the characters occurred in the string and Set2 records those nodes whose indegree is bigger than zero. Specifically if the size of map equals to the size of set2, which means all nodes\' indegree is one. Everyone got included in loop. That\'s terrible, I have to return false.\n\nBut before that , I can check the size of set1. Maybe someone can be used as transfer station directy due to its unoccurance. And maybe the size of map is zero or one, we need only one or zero conversions. That\'s obviously we need to return true.\n```\nclass Solution {\n //@para map records all the conversion relation\n //@para set1 records who occured in the string\n //@para set2 records thosed nodes whose indegree >0\n Map map=new HashMap<>();\n Set set1=new HashSet<>();\n Set set2=new HashSet<>();\n public boolean canConvert(String str1, String str2) {\n int p=0;\n while(p<=str1.length()-1)\n {\n set1.add(str1.charAt(p));\n if(str1.charAt(p)==(str2.charAt(p)))\n p++;\n else\n {\n if(map.containsKey(str1.charAt(p)))\n {\n if(map.get(str1.charAt(p)).equals(str2.charAt(p)))\n p++;\n else //must be one to one relation otherwise return false directly\n return false;\n }\n else\n {\n set2.add(str2.charAt(p));\n map.put(str1.charAt(p),str2.charAt(p));\n p++;\n }\n }\n }\n if(set1.size()<=25||map.size()<=1) //at least one node never occurred before or only no loop in the graph\n return true;\n if(map.size()>set2.size())//at least one node out of the loop\n return true;\n return false;\n }\n}\n```\n\n

String Transforms Into Another String

Problem Description

Problem Description

Answer Panel