LeetCode[排序] - #242 Valid Anagram

原题链接：#242 Valid Anagram

 

要求：

给定两个字符串s和t，写一个函数，判断t是否是s的变位词。

如果t跟s包含相同字符但排列顺序不同，则称t是s的变位词。

例如：

s = "anagram", t ="nagaram"，返回true

s = "rat", t = "car"，返回false

注意：可以假定字符串只包含小写字母。

 

难度：容易

 

分析：

解这个问题有两种思路，由于题目限定字符串中只包含小写字母，那么分别计算两个字符串中每个字母出现次数，然后再比较即可。第二种思路是把字符串看作字符数组，将两个字符数组分别排序，所得结果若相同，则说明两个字符串互为变位词。

 

解决方案：

Java - 342ms

    public boolean isAnagram(String s, String t) {
        if(s==null||t==null||s.length()!=t.length()){
            return false;
        }
        char[] array1 = s.toCharArray();
        char[] array2 = t.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        return Arrays.equals(array1, array2);
    }

上述解决方案中直接使用了Arrays.sort()方法来为两个数组排序，当然，也可以自己实现排序算法。最常用的冒泡和快排：

 

冒泡排序：

    public void bubbleSort(char[] array) {
        for(int i=0; i<array.length-1; i++){
            for(int j=0; j<array.length-i-1; j++){
                if(array[j]>array[j+1]){
                    char temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }yi
        }
    }

快速排序： 

public void quickSort(char[] array, int low, int high) {
        if(low>=high){
            return;
        }
        char paviot = array[low];
        int l = low+1, h = high;
        while(l<h){
            while(array[h]>=paviot && l<h){
                h--;
            }
            while(array[l]<=paviot && l<h){
                l++;
            }
            if(l<h){
                char tmp = array[l];
                array[l] = array[h];
                array[h] = tmp;
            }
        }
        if(array[low]>array[l]){
            array[low] = array[l];
            array[l] = paviot;
        }
        quickSort(array, low, l-1);
        quickSort(array, l+1, high);
    }

冒泡排序时间复杂度为O(n2)，快排为O(nlogn)。八大排序算法一文对各排序算法有比较好的总结，在此不再赘述。事实上，查看Arrays.sort()的实现可知，它所使用的是一个改进的双paviot的快速排序算法。可参见java.util.DualPivotQuicksort。

 

简单测试程序

 

评论

3 楼 kyzaqlx 2015-09-09  

用两个hash表，O(N)

public boolean isAnagram(String str0, String str1) {
        if ((null == str0) || (null == str1)) {
            return false;
        }
        
        int length0 = str0.length();
        int length1 = str1.length();
        if (length0 != length1) {
            return false;
        }
        
        int count = 26;
        int[] array0 = new int[count];
        for (int i=0; i<length0; i++) {
            array0[str0.charAt(i) - 'a']++;
        }
        
        int[] array1 = new int[count];
        for (int i=0; i<length1; i++) {
            array1[str1.charAt(i) - 'a']++;
        }
        
        return Arrays.equals(array0, array1);
    }

2 楼 Cwind 2015-08-12  

cywhoyi 写道

两个stack，是不是也行啊？O(N)

介绍下算法思路？我还没想明白用stack该怎么做

1 楼 cywhoyi 2015-08-12  

两个stack，是不是也行啊？O(N)