Java中的Anagram算法

我想制作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

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

 // 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 2

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

 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 3

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

这段代码很好地certificate了为什么你应该总是在你的if周围有curly braces ，即使只有一个语句。 你的第二个任务实际上在if-condition ，并且总会发生。

检查两个字符串是Anagram的最佳方法是将它们转换为字符数组(String#toCharArray) 。 然后使用Arrays.sort方法对它们进行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

我不确定你要做什么，但我很确定它不会工作（它运行在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 5

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

 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 6

它不起作用的原因：

以“des”和“sed”为例。

在它匹配的最后一次迭代中，它将评估：

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

这将是：if（“s”==“s”）

然后它将进入if块，并进行评估

 newStr = "sed".replace("s",""); 

这将给你“ed”，而不是一个空字符串。

这个故事的寓意是你总是用s2替换字符而不是一个字符，这个字符永远不会是空的。

无论如何，使用String.replace（）是错误的，因为默认情况下它将替换该字符的所有实例。 使用String.replace（），它会认为“sed”是“seeeeeeed”的字谜。 你最好使用String.replaceFirst（）。

无论如何，一个起点是进行以下修改：

 String newStr = s2; ... // inside if block newStr = newStr.replaceFirst( delStr, "" ); 

Answer 7

下面是一个简明的代码片段，用于确定两个字符串在两个字符串的单个迭代中是否为字符串，以及256个元素数组的最终迭代。 此方法通过在映射数组中记录字符计数来避免对字符串中的字符进行排序并转换为/从Strings / char数组转换。

 static boolean isAnagram(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); int[] charMap = new int[256]; for (int i = 0; i < n; i++) { char c1 = s1.charAt(i); charMap[c1]++; char c2 = s2.charAt(i); charMap[c2]--; } for (int i = 0; i < charMap.length; i++) { if (charMap[i] != 0) return false; } return true; } 

该代码基本上递增和递减对应于字符的数组中的索引位置。 如果任何数组元素在迭代结束时不为零，则会有不等量的增量和减量，因此字符串包含不同的字符，并且不能是彼此的字符。

鉴于该算法迭代两个相同大小的字符串一次，运行时为O（n）。 空间复杂度为O（1），因为charMap始终是恒定的，具体取决于charset要求。

Answer 8

只是确定，你试图检查s1是否是s2的字谜正确吗？ 这也意味着s2是s1的字谜。 所以我只是对s1和s2进行排序并检查它们是否相等。

 String string1 = "fdafdas"; String string2 = "fdwqkjl"; char[] chars = string1.toCharArray(); char[] chars2 = string2.toCharArray(); Arrays.sort(chars); Arrays.sort(chars2); string1 = new String(chars); string2 = new String(chars2); if (string1.equals(string2)) { //They are an anagram } 

Answer 9

 public boolean isAnagram(String a, String b) { boolean result = false; final String one = a.replaceAll("[\\s+\\W+]", "").toLowerCase(); final String two = b.replaceAll("[\\s+\\W+]", "").toLowerCase(); if (one.length() == two.length()) { final char[] oneArray = one.toCharArray(); final char[] twoArray = two.toCharArray(); Arrays.sort(oneArray); Arrays.sort(twoArray); result = Arrays.equals(oneArray, twoArray); } return result; } 

Answer 10

O（n）解决方案没有任何排序并且只使用一个映射。 还在其他解决方案中添加了正确的空检查。

 public boolean isAnagram(String leftString, String rightString) { if (leftString == null || rightString == null) { return false; } else if (leftString.length() != rightString.length()) { return false; } Map occurrencesMap = new HashMap<>(); for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); int nrOfCharsInLeft = occurrencesMap.containsKey(charFromLeft) ? occurrencesMap.get(charFromLeft) : 0; occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); int nrOfCharsInRight = occurrencesMap.containsKey(charFromRight) ? occurrencesMap.get(charFromRight) : 0; occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(int occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

而不是通用的解决方案，但速度要快一点：

 public boolean isAnagram(String leftString, String rightString) { if (leftString == null || rightString == null) { return false; } else if (leftString.length() != rightString.length()) { return false; } char letters[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; Map occurrencesMap = new HashMap<>(); for (char l : letters) { occurrencesMap.put(l, 0); } for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); Integer nrOfCharsInLeft = occurrencesMap.get(charFromLeft); occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); Integer nrOfCharsInRight = occurrencesMap.get(charFromRight); occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(Integer occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

Answer 11

这是一个主要依赖java的简单方法完整的代码在这里https://github.com/rdsr/algorithms/blob/master/src/jvm/misc/AnagramsList.java （注意这解决了一个相关的不同问题）

 class Anagram { Map anagram; Anagram(String s) { anagram = new HashMap(); for (final Character c : s.toCharArray()) { if (anagram.containsKey(c)) { anagram.put(c, 1 + anagram.get(c)); } else { anagram.put(c, 1); } } } @Override public int hashCode() { //.. elided } @Override public boolean equals(Object obj) { //.. elided } } public class Anagrams { public static void main(String[] args) { System.out.println(new Anagram("abc").equals(new Anagram("bac"))); } } 

Answer 12

使用位向量方法为anagram子串提供更快的版本

 public boolean isAnagram(String _source1, String _source2) { int flag = 0, char_index = 0, counter = 0; if(_source2.length() < _source1.length()){ return false; } char[] _stringchar = _source1.toCharArray(); char[] _tocheck = _source2.toCharArray(); for(char character : _stringchar) { char_index = character - 'a'; if((flag & (1 << char_index)) == 0) flag |= (1 << char_index); } for(char toCheckcChar : _tocheck) { char_index = toCheckcChar - 'a'; if((flag & (1 << char_index)) > 0) counter++; else counter = 0; if(counter == _source1.length()) return true; } return false; } 

Answer 13

原因很简单，因为replace函数会创建一个新的String对象。 它对实际的字符串没有任何作用（在你的情况下是s2 ），因为在Java中，字符串本质上是最终的。 正如cmonkey所指出的，你总是从字符串s2中删除一个字符，但实际上创建了一个新的String对象，其中1个字符少，s2保持原样。

在你的情况下使这个工作的简单方法是创建一个新的字符串对象并将其分配给自己。

 { s2=s2.replace(delString,""); .... if(s2.empty()) return true; return false; } 

Answer 14

有一次我做了关于字谜的面试的考试。 我把它上传到我的github帐户。 java代码检查文本文件（具有多行）是anagram诗还是anagram文本。

https://github.com/javocsoft/anagram_poem_checker

希望能帮助到你！

再见。

Answer 15

只需看看newStr = s2.replace（delStr，“”）;

你在这里做什么来替换s2中的char并分配回newStr，意味着你没有改变s2中的任何东西。 只需将此代码替换为下面的代码即可

=中newstr newStr.replace（delStr， “”）;

Answer 16

我花了一些时间来实际写下逻辑并写一个代码来检查两个字符串，如果它们是字谜或不是字谜。 当然借助上述答案！ XD

 public static void main(String[] args) { Map char_map = new HashMap(); Map empty_map = new HashMap(); String a = "HelloP"; String b = "HePlol"; if (a.length() != b.length()) { System.out.println("false"); System.exit(0); } for (char c : a.toLowerCase().toCharArray()) { empty_map.put(c, 0); if (char_map.containsKey(c)) char_map.put(c, 1 + char_map.get(c)); else char_map.put(c, 1); } for (char c : b.toLowerCase().toCharArray()) if (char_map.containsKey(c)) char_map.put(c, char_map.get(c) - 1); System.out.println(char_map.equals(empty_map)); } 

Answer 17

我认为这适用于复杂性O（2n）

 public static boolean isAnagram(String str1, String str2){ if(str1.length() != str2.length()){ return false;} int[] buffer = new int[256]; for(char ch : str1.toCharArray()){ buffer[ch]++; } for(char ch : str2.toCharArray()){ if(buffer[ch]==0) return false; buffer[ch] = (buffer[ch] > 0)?(buffer[ch] - 1 ): -1 ; } return true; } 

Answer 18

这是我为使用数组而不是HashMap编写的Java实现。 这节省了空间，而且arrays非常快。

 public static boolean anagram(String s, String t) { if (s.length() != t.length()) return false; int[] arr = new int[123]; for (char c : s.toCharArray()) arr[c]++; for (char c : t.toCharArray()) arr[c]--; for (int i : arr) if (i != 0) return false; return true; } 

Answer 19

 import java.util.Scanner; public class JavaProgram { public static void main(String[] input) { String str1, str2; int len, len1, len2, i, j, found=0, not_found=0; Scanner scan = new Scanner(System.in); System.out.print("Enter First String : "); str1 = scan.nextLine(); System.out.print("Enter Second String : "); str2 = scan.nextLine(); len1 = str1.length(); len2 = str2.length(); if(len1 == len2) { len = len1; for(i=0; i 

Answer 20

 public class Anagram { public boolean isAnagram( String left, String right) { if (left.length() == right.length()) { Map map = new HashMap<>(); char[] a = left.toCharArray(), b = right.toCharArray(); for (int i = 0; i < a.length; i++) { accumulate(map, a[i]); accumulate(map, b[i]); } for (char c : map.keySet()) { if (map.get(c) > 0) { return false; } } return true; } else { return false; } } private void accumulate( Map map, char key) { if (map.containsKey(key)) { map.put(key, Math.abs(map.get(key) - 1)); } else { map.put(key, 1); } } } 

Answer 21

这是我方面的解决方案

 private static boolean isAnagram(String s1, String s2){ int count = 0; boolean flag = false; if(s1.length() != s2.length()){ return false; } //checks whether both word's letters are the same for (int i = 0; i < s1.length(); i++){ for (int j = 0; j < s2.length(); j++){ if(s1.charAt(i) == s2.charAt(j)){ count++; break; } } } //if count equals to one of the Strings length then it is an anagram if(count == s2.length() ){ flag = true; } return flag; } 

Answer 22

  String str1="Mother In Law"; String str2="Hitler Woman"; char[] anag1=str1.replaceAll("\\s", "").toLowerCase().toCharArray(); char[] anag2=str2.replaceAll("\\s", "").toLowerCase().toCharArray(); Arrays.sort(anag1); Arrays.sort(anag2); System.out.println(Arrays.equals(anag1, anag2)? "words are anagrams":"words are not anagrams"); 

Answer 23

我想以下解决方案有O(n)复杂性，如果有人不同，请告诉我。

 import java.util.HashMap; import java.util.Scanner; public class Anagrams { static boolean isAnagram(String word1, String word2) { if(word1.length() != word2.length()) { return false; } int flag=0; HashMap table = new HashMap(); for(int i=0; i< word1.length();i++) { table.put(word1.charAt(i),1); } for(int i=0; i< word2.length();i++) { if(table.containsKey(word2.charAt(i))) { continue; } else { flag=1; break; } } return flag == 0; } public static void main(String[] args) { System.out.println("Enter your string"); Scanner sc= new Scanner(System.in); String word1= sc.nextLine(); String word2=sc.nextLine(); boolean result = isAnagram(word1,word2); if(result) { System.out.println("The words are Anagrams"); } else{ System.out.println("The words are not Anagrams"); } } } 

Answer 24

 public static boolean isAnagram(String s1, String s2) { boolean aux = true; if (s1.length() != s2.length()){ aux = false; }else{ for (int i = 0; i < s1.length(); i++) if(s2.toUpperCase().indexOf(s1.toUpperCase().substring(i, i+1)) == -1) aux = false; } return aux; } 

Answer 25

 import java.util.Scanner; public class Anagrams { static boolean isAnagram(String a, String b) { a = a.toLowerCase(); b = b.toLowerCase(); if (a.length() != b.length()) { return false; } char[] chars = a.toCharArray(); for (char c : chars) { int index = b.indexOf(c); if (index != -1) { b = b.substring(0, index) + b.substring(index + 1, b.length()); } else { return false; } } return b.isEmpty(); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String a = scan.next(); String b = scan.next(); scan.close(); boolean ret = isAnagram(a, b); System.out.println((ret) ? "Anagrams" : "Not Anagrams"); } } 

Answer 26

 import java.util.*; class Anagrams { public static void main(String[] args) { System.out.println("Enter the two words"); Scanner scan = new Scanner(System.in); String word1 = scan.next(); String word2=scan.next(); StringBuilder sb1= new StringBuilder(word1); StringBuilder sb2= new StringBuilder(word2); int count=0; System.out.println("length ! "+sb1.length()); System.out.println("Length ! "+sb2.length()); if(sb1.length()==sb2.length()){ for(int i=0;i