String

本学习计划适用于那些想要准备技术面试但不确定他们应该关注哪些问题的人。这些问题经过精心策划，因此 Level 1和 Level 2 将指导初级和中级用户解决涵盖大多数中端公司面试所需的数据结构和算法的问题。而 Level 3 用来帮助以顶级公司为目标的学习小伙伴。

本学习计划的题目小编解答在英文版 LeetCode 中尽可能超越 100% 提交。

---

第一题：同构字符串

从题目条件中可以分析出，该题可归为数学中的映射：

• “每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序”，代表字符集合 s , t 之间是满射；
• “相同字符只能映射到同一个字符上，不同字符不能映射到同一个字符上”，代表字符集合 s , t 之间是单射。

百度百科：

映射的不同分类是根据映射的结果进行的，从下面的三个角度进行：

1．根据结果的几何性质分类：满射（到上）与非满射（内的）

2．根据结果的分析性质分类：单射（一一的）与非单射

3．同时考虑几何与分析性质：满的单射（一一对应）。

说到这，读者朋友肯定会说这其实就可以用 HashMap 来解答，但是小编认为，此题中还给了一个隐含条件，那就是字符范围是 ASCII 码，也就意味着使用一个 128 长度的数组（空间复杂度 O(1)）是可以替换复杂度较高的 HashMap 来解答的。

那么，用一维数组如何解决一一映射且不会映射到不同字符上呢？

小编使用的方法是，根据字符的 ASCII 值找到数组中所在的下标位置，在该位置记录此字符当前在源串中出现的是第几个字符。如 egg 中 e 是第 1 个字符，g 是第 2 个字符，如图所示。同样的 add 也是一样的操作。

1. 此时遍历第 3 个字符 g & d 时，因为 g & d 此前对应的是值是 2 ，所以可继续更新出现在了第 3 个位置，更新 103 => 3 和 100 => 3；
2. 假设 egg => eggg ，而 add => adde ，此时 adde 中的 e 对应是初始值，而 eggg 中 g 对应的是 3，出现不同值，所以可判断为不同构了。

public class IsomorphicStrings {
    public boolean isIsomorphic(String s, String t) {
        int[] sToT = new int[128];
        int[] tToS = new int[128];

        for(int i = 0; i < s.length(); i++){
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);

            if (sToT[sChar] != tToS[tChar]) {
                return false;
            }

            sToT[sChar] = i+1;
            tToS[tChar] = i+1;
        }

        return true;
    }
}

第二题：判断子序列

分析此题，思路应该是非常明确的，长字符串中过滤多余的字符串后能得到短串即是正确。所以可利用循环比较的方法来过滤。

Gif 展示的是刚好符合的结果，如果当长字符串遍历结束，短串还未到达终点时，说明是不符合子序列条件的。

public class IsSubsequence {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        int sLen = s.length();
        int tLen = t.length();

        for (; i < tLen && j < sLen; i++) {
            char cT = t.charAt(i);
            char cS = s.charAt(j);

            if (cT == cS) {
                j++;
            }
        }

        return j == sLen;
    }
}

---

代码仓库：https://github.com/chaffz/leetcode-java