Java中的Anagram算法

Question

我想制作anagram算法,但这段代码不起作用.我的错在哪里？例如des和sed是anagram但输出不是anagram同时我必须使用string方法.不是数组.:)

public static boolean isAnagram(String s1 , String s2)
{
    String delStr="";
    String newStr="";

    for(int i=0;i<s1.length();i++)
    {
        for(int j=0 ; j < s2.length() ; j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {
                delStr=s1.substring(i,i+1);
                newStr=s2.replace(delStr,"");
            }
        }           
    }

    if(newStr.equals(""))
        return true;
    else
        return false;
}

Answer 1

一种更简单的方法可能是只对两个字符串中的字符进行排序,并比较它们是否相等:

public static boolean isAnagram(String s1, String s2){

        // Early termination check, if strings are of unequal lengths,
        // then they cannot be anagrams
        if ( s1.length() != s2.length() ) {
            return false;
        }
        s1=s1.toLowerCase();
        s2=s2.toLowerCase();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        String sc1 = new String(c1);
        String sc2 = new String(c2);
        return sc1.equals(sc2);
}

我个人认为它比嵌套for-loops = p更具可读性

这具有O(n log n)运行时复杂度,其中n是较长字符串的长度.

编辑:这不是最佳解决方案.请参阅@ aam1r的答案,了解最有效的方法(即您在采访中应该说些什么)

Answer 2

这可以使用恒定空间在线性时间内完成.这是帮助您入门的伪代码:

// Create new hashtable/hashmap to keep track of how many times each character
// is being used
character_map -> new hash map

// Initial check. If lengths are not the same, they can't be anagrams.
if s1.length != s2.length:
    throw exception "Not anagrams"

// Add all characters from s1 to hashmap. Increment the value to keep track of
// number of occurences
foreach character c1 in s1:
    character_map[c1]++

// Iterate through all character in s2 and decrement count of each character.
foreach character c2 in s2:
    character_map[c2]--

// If they are anagrams, each character should be at "0" count at the point.
// If we come across a character that is not, it means that they are not anagrams
foreach key k, value v in character_map:
    if v != 0:
            throw exception "Not anagrams"

此代码不排序,因此可以使用简单循环完成.总运行时间为O(n),总空间为O(1) - 因此是最快的解决方案.哈希映射中可以包含的元素数量是不变的(即您知道字母表集中有多少项).

Answer 3

if(s1.charAt(i)==s2.charAt(j))
        delStr=s1.substring(i,i+1);
        newStr=s2.replace(delStr,"");

这段代码很好地证明了为什么你应该总是拥有curly braces你的if,即使只有一个语句.你的第二个任务实际上是在if-condition,并且将永远发生.

检查两个字符串的最佳方法Anagram是将它们转换为字符数组(String#toCharArray).然后用Arrays.sort方法对它们进行排序 并对它们进行比较.

更新 : -

如果你只想使用String方法,那么你实际上并不需要嵌套循环.你可以只用一个.

这是您的修改后的代码: -

public static boolean isAnagram(String s1 , String s2){

    if (s1.length() != s2.length()) {
        return false;
    }

    for(int i = 0; i < s2.length(); i++) {

            if( !s1.contains("" + s2.charAt(i))) {
                return false;
            }

            s1 = s1.replaceFirst("" + s2.charAt(i), "");
            s2 = s2.replaceFirst("" + s2.charAt(i), "");
    }
    return true;
}

Answer 4

更有效的是按排序顺序比较字符串.

public static boolean isAnagram(String s1 , String s2) {
    return s1.length() == s2.length() 
        && checkSum(s1) == checkSum(s2)
        && Arrays.equals(lettersSorted(s1), lettersSorted(s2));
}

static long checkSum(String s) {
    long sqrSum = 0;
    for(int i = 0; i < s.length(); s++) {
       char ch = s.charAt(i);
       sqrSum += ch + (1L << ch);
    }
}

static char[] lettersSorted(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    return chars;
}

这是一个O(N ln N)算法,但如果字符串通常不是字谜,则平均为O(N).

Answer 5

我不确定你要做什么,但我很确定它不会起作用(而且它会运行O(n^2).试试这个(运行中O(n log n))代替:

public static boolean isAnagram(String s1, String s2){
  if (s1.length() != s2.length()) return false;

  char[] c1 = s1.toCharArray();
  char[] c2 = s2.toCharArray();

  Arrays.sort(c1);
  Arrays.sort(c2);

  for(int i = 0; i < c1.length; i++) {
    if(c1[i] != c2[i]) return false;
  }

  return true;
}

Answer 6

有多种可能的解决方案来确定字符串是否为 Anagram。\n1. 使用Array.sort()预定义方法

\n\n

String string1 = "abc";\nString string2 = "bca";\nchar[] chars = string1.toCharArray();\nchar[] chars2 = string2.toCharArray();\nArrays.sort(chars);\nArrays.sort(chars2);\nstring1 = new String(chars);\nstring2 = new String(chars2);\nif (string1.equalsIgnoreCase(string2)) {\n  System.out.println("Anagram");\n} else {\n  System.out.println("Not Anagram");\n}\n

\n\n

时间复杂度：\xce\xa9(n log n)\n2。通过迭代法

\n\n

char [] charArray = str.toCharArray();\nif(str.length() == str1.length()){\n    for(char ch : charArray){\n        if(str1.indexOf(ch) == -1){\n            System.out.println("Not Anagram");\n        } \n    }    \n    System.out.println("Anagram");\n} else {\n    System.out.println("Not Anagram");\n}\n

\n\n

时间复杂度：\xce\xa9(n)

\n\n

不过，第一个算法更具可读性，第二个算法确实执行得更快。

\n