LintCode刷题之路(一)

Z时代
2024-01-10
分类：综合

coding

在算法和数据结构上，我觉得我是一个彻彻底底的小白，开始刷题吧。

#阶梯训练

###1. 两个字符串是变位词

######写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

样例

给出 s = "abcd"，t="dcab"，返回 true.

给出 s = "ab", t = "ab", 返回 true.

给出 s = "ab", t = "ac", 返回 false.

首先看到这个题目我们想到的就是字符串排序了，通过排序把字符调换成有顺序的字符串，再来比较。

所以就会出现以下代码

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        //先查看长度是否相等，不相等则返回false
        if(s.length() != t.length()){
            return false;
        }
        //转换成字符 然后排序
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        Arrays.sort(sChar);
        Arrays.sort(tChar);
        for(int i=0;i<s.length();i++){
            if(sChar[i]!=tChar[i]){
                return false;
            }
        }
        return true;
    }
};

由于以上是两个字符串之间的比较，所以就能很方便的这样用，但是如果是多个字符串数组又是怎么比较的呢，这个问题后面会有。

九章算法提供的答案是

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        if (s.length() != t.length()) {
           return false;
        }
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }
};