IsomorphicStrings [source code]

public class IsomorphicStrings {
static
/******************************************************************************/
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        return getCountString(s).equals(getCountString(t));
    }

    public String getCountString(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] nums = new int[128];
        int counter = 1;
        for (char c : chs) {
            if (nums[c] == 0) nums[c] = counter++;
        }
        StringBuilder sb = new StringBuilder();
        for (char c : chs) {
            sb.append(nums[c]);
        }
        return sb.toString();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        IsomorphicStrings.Solution tester = new IsomorphicStrings.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));
        }
    }
}

刚开始依赖的核心算法是这个:

    public String getCountString(String s) {  
        char[] chs = s.toCharArray();  
        int n = chs.length;  
        int[] counts = new int[128];  
        for (char c : chs) {  
            counts[c]++;  
        }  
        StringBuilder sb = new StringBuilder();  
        for (char c : chs) {  
            int count = counts[c];  
            if (count != 0) {  
                sb.append(count);  
                counts[c] = 0;  
            }  
        }  
        return sb.toString();  
    }

但是这个算法有问题, 第四个 case 就 break 了; 当时想这个算法的时候脑子里都是paper & title的这个例子, 没有想到其他的情况;

最后这一题实际的算法其实更简单一些, 就是做一个直观的 count and translate就行了, 算法本身没有什么好说的, 最后的速度是10ms (75%).

这个是 discussion 最优解:

class Solution {  
public:  
    bool isIsomorphic(string s, string t) {  
        int m1[256] = {0}, m2[256] = {0}, n = s.size();  
        for (int i = 0; i < n; ++i) {  
            if (m1[s[i]] != m2[t[i]]) return false;  
            m1[s[i]] = i + 1;  
            m2[t[i]] = i + 1;  
        }  
        return true;  
    }  
};

这个思路是差不多的, 不过代码简洁很多, 而且他这里用的也是一个 translate 的思路, 不过 translate 的 value, 不用单独找一个 int, 而是直接用 index 来做就可以了, 这个很聪明; 注意这里的+1是因为不像让最后 translate 的 value 包含0, 因为初始值全都是0;
//这个好像跟我的算法有区别, 另外一个类似算法的作者的解释是:
The main idea is to store the last seen positions of current (i-th) characters in both strings.
我刚开始思考的时候想的都是 yes-case, 所以感觉其实未必是rightmost occurrence index, 所以如果m1[s[i]] != m2[t[i]]的 test 通过了, 那么没有必要在下面更新这两个 entry 的值. 但是如果你考虑 no-case, 就知道一定要更新;
虽然说的是"保证right most occurrence index相等", 实际上完成的是一个"保证all occurrence index相等": 因为每一次更新这个 index, 都会先check equality;

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