Leetcode 有效的字母异位词

一颗蔬菜 2019-09-07 PM 43℃ 0条

原题链接

题目中说明了字符串只包含小写字母,遍历s,若在t中也找到同样的字母就将它置为A,找不到时返回false

这么做思路很简单,时间复杂度为O(n^2),提交时显示运行超时了。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] sStr = s.toCharArray();
        char[] tStr = t.toCharArray();
        for (int i = 0; i < sStr.length; i ++) {
            boolean isFound =  false;
            for(int j = 0; j < tStr.length; j ++) {
                if (sStr[i] == tStr[j]) {
                    tStr[j] = 'A';
                    isFound = true;
                    break;
                }
            }
            if (isFound == false) {
                return false;
            }
        }
        return true;
    }
}

尝试另一种思路,字母异位说白了就是排序之后两个字符数组相等。这种方法的时间复杂度是O(nlogn+n)。还是不够快。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length())return false;
        char[] ss=s.toCharArray();
        char[] ts=t.toCharArray();
        Arrays.sort(ss);
        Arrays.sort(ts);
        return Arrays.equals(ss,ts);
    }
}

在评论区里看到大佬的做法,妙啊!

算法思想就是统计s中的每个字母的出现次数,将次数存入到数组b中,然后每遍历t中的一个,将其在b中的次数减1。如果st是有效异位词,那么最终b中的每一个元素都是0。这种解法的关键是将26个字母哈希映射为b的下标。时间复杂度为o(n)

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] b = new int[26];
        for(int i = 0; i < s.length(); i++) 
            b[s.charAt(i) - 'a']++;
        for(int i = 0; i < t.length(); i++) 
            if(--b[t.charAt(i) - 'a'] < 0) 
            return false;
        return s.length() == t.length();
    }
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。