IsomorphicStringsOPT [source code]

public class IsomorphicStringsOPT {
static
/******************************************************************************/
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        // 5ms solution: use small arrays simulating a lookup tables since all the test cases use ASCII characters.
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        char[] mapS = new char[128];
        char[] mapT = new char[128];
        char tempS, tempT;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            tempS = ss[i];
            tempT = tt[i];
            if (mapS[tempS] == 0 && mapT[tempT] == 0) {
                mapS[tempS] = tempT;
                mapT[tempT] = tempS;
            } else {
                if (mapS[tempS] != tempT || mapT[tempT] != tempS) return false;
            }
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        IsomorphicStringsOPT.Solution tester = new IsomorphicStringsOPT.Solution();
        String[] inputs = {
            "egg", "add",
            "foo", "bar",
            "paper", "title",
            "abba", "abab",
        };
        int len = inputs.length;
        for (int i = 0; i < len / 2; i++) {
            String s = inputs[0 + 2 * i];
            String t = inputs[1 + 2 * i];
            System.out.println(s + " VS " + t + " -> " + tester.isIsomorphic(s, t));
        }
    }
}

这个是 submission 最优解: 3(98);

本身算法并没有什么复杂的地方, 主要的原理就是通过两个数组来完成一个两个 string 之间的字母的映射关系, 是一个mapping, 而不是我的 translating. 最后的速度却比我的快很多, 感觉有可能是跟我使用了 StringBuilder 有关系: 他这里的操作基本都是 char;

Problem Description

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Difficulty:Easy
Category:Algorithms
Acceptance:33.58%
Contributor: LeetCode
Companies
linkedin
Related Topics
hash table
Similar Questions
Word Pattern