if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all
occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters
may map to the same letter, but a letter may map to itself.
Example:
given "foo", "app"; returns true
we can map 'f' -> 'a' and 'o' -> 'p'
given "bar", "foo"; returns false
we can't map both 'a' and 'r' to 'o'
given "turtle", "tletur"; returns true
we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r'
given "ab", "ca"; returns true
we can map 'a' -> 'c', 'b'
Click here for the original problem.
I implement two methods, the first one map the character to the first occurred index for both strings, and check if the encodings are the same for both strings. The second one is more traditional, map characters in the first string to the same index one in the second string. However, both methods require two maps.
import java.util.*; public class IsomorphicString { //map index public boolean isIsomorphic(String a, String b) { if (a.length() != b.length()) return false; a = a.toLowerCase(); b = b.toLowerCase(); Mapamap = new HashMap (); Map bmap = new HashMap (); for (int i = 0; i < a.length(); i++) { if (!amap.containsKey(a.charAt(i))) amap.put(a.charAt(i), i); if (!bmap.containsKey(b.charAt(i))) bmap.put(b.charAt(i), i); } for (int i = 0; i < a.length(); i++) { if (amap.get(a.charAt(i)) != bmap.get(b.charAt(i))) return false; } return true; } //map character public boolean isIsomorphic2 (String a, String b) { if (a.length() != b.length()) return false; a = a.toLowerCase(); b = b.toLowerCase(); Map amap = new HashMap (); Map bmap = new HashMap (); for (int i = 0; i < a.length(); i++) { if (amap.containsKey(a.charAt(i))) { if(amap.get(a.charAt(i)) != b.charAt(i)) return false; } if (bmap.containsKey(b.charAt(i))) { if (bmap.get(b.charAt(i)) != a.charAt(i)) return false; } amap.put(a.charAt(i), b.charAt(i)); bmap.put(b.charAt(i), a.charAt(i)); } return true; } }
No comments:
Post a Comment