Java中的字谜算法

Question

我想制作一个字谜算法，但是这段代码不起作用。我的问题在哪里？ 例如des和sed是字谜，但输出并不是字谜。 与此同时，我必须使用字符串方法，而不是数组。:)

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;
}

- SemihY

---

你能解释一下你发现了什么问题吗？出现了异常吗？它只是没有返回你预期的结果吗？还是进入了无限循环？ - Mike Clark

你能举个例子说明在你的情况下什么是“Anagram”吗？ - Rohit Jain

不，只有我写了des和sed但输出不是回文。 - SemihY

为什么你的代码不工作？因为每次匹配成功后，你都用s2（少一个字母）覆盖了newStr。例如，如果s2是ab，当你匹配到b时，newStr变成了a，然后当你匹配到a时，newStr并没有变为空字符串，而是变成了b（因为它是s2减去匹配字符）。这不是你代码中唯一的错误（重复字符、长度不同的字符串），但这是你首先会看到的错误。 - Konstantin Tarashchanskiy

可能值得注意的是，经过这么长时间，Java已经进步到足以将其变成一行代码：Arrays.equals( a.chars().filter(Character::isAlphabetic).sorted().toArray(), b.chars().filter(Character::isAlphabetic).sorted().toArray()); - Gene

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循环更易读 =p

此算法的运行时间复杂度为O(n log n)，其中n是较长字符串的长度。

编辑：这不是最优解。请查看@aam1r的答案以获取最有效的方法（即在面试中应该说的内容）

- sampson-chen

---

你可以使用Arrays.equals()方法来比较已排序的数组。 - Peter Lawrey

很遗憾，"不起作用"并没有给我任何可以帮助你的信息 =( - sampson-chen

@durron597 - 是的，aam1r的答案是最优解，请投票支持它。 - sampson-chen

@sampson-chen，您能否解释一下logn是从哪里来的？ - Ömer Faruk Almalı

@ÖmerFarukAlmalı O(n log n) 是基于比较的排序算法之一：http://en.wikipedia.org/wiki/Comparison_sort - sampson-chen

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) - 因此是最快的解决方案。哈希映射中可以拥有的元素数量是恒定的（即您知道字母表集中有多少项）。

- Aamir

---

啊哈，桶排序，我的英雄。+1。顺便说一下，这是O(1)空间复杂度，不是O(n)。 - durron597

如果长度不同，它们就不能成为变位词。 -> 首先去掉空格。 - Koray Tugay

Answer 3

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

这段代码很好地展示了为什么你应该始终在if语句周围加上花括号，即使只有一个语句。你的第二个赋值实际上是在if条件之外的，因此会一直发生。

检查两个字符串是否是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;
}

- Rohit Jain

---

@GanGnaMStYleOverFlowErroR：这个帖子现在有三个正确的答案，它们的点赞数都少于这个答案。Rohit，你应该现在给自己颁发“自律徽章” ;) - durron597

@durron597.. 哈哈.. 你真的想让我拥有那个吗？:( 我已经更新了我的答案，虽然没有代码，因为OP已经得到了3个。 - Rohit Jain

@durron597。这是你要的。我添加了一段代码，使它成为一个有效的答案。 ;) - Rohit Jain

@RohitJain：什么，你不想要一个“守纪律”徽章吗？ :) 另外，那段代码不起作用，请考虑字符串“abbbccc”和“aaaaabc”。 - durron597

@durron597.. 不 :( 我一直被认为是一个不守纪律的人。我不想失去这个形象。 - Rohit Jain

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)。

- Peter Lawrey

---

哈哈，到目前为止我们已经有三个人了 - 伟大思想的格言，是吧？ ;) - sampson-chen

@sampson-chen，所以我添加了一些不同的东西。 ;) - Peter Lawrey

@PeterLawrey 哈哈，那样会更快，可惜我已经给你点赞了 ;) - durron597

这里的checkSum方法有什么作用？ - arsenal

@lining checkSum 的目的是执行 O(n) 检查，通常可以检测出哪些字符串不匹配。 - Peter Lawrey

除了检查总和之外，您还可以在同一个循环中检查XOR。总和和XOR的组合应该使“碰撞”变得更加罕见。 - kaya3

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;
}

- durron597

---

如果您想检查长度，我建议在调用 toCharArray 之前进行检查。 - Peter Lawrey

这里的for循环可以替换为return Arrays.equals(c1, c2);。https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#equals-char:A-char:A- - kaya3

Answer 6

有多种方法可以确定一个字符串是否是变位词。 1. 使用预定义方法Array.sort()

String string1 = "abc";
String string2 = "bca";
char[] chars = string1.toCharArray();
char[] chars2 = string2.toCharArray();
Arrays.sort(chars);
Arrays.sort(chars2);
string1 = new String(chars);
string2 = new String(chars2);
if (string1.equalsIgnoreCase(string2)) {
  System.out.println("Anagram");
} else {
  System.out.println("Not Anagram");
}

时间复杂度：Ω(n log n) 2. 迭代方法

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

时间复杂度：Ω(n)

虽然第一个算法更易读，但第二个算法执行速度更快。

- Vhndaree

---

如果您想以不区分大小写的方式测试变位词，应在排序之前将两个字符串转换为小写（或大写）。否则，{'Z'，'a'}和{'A'，'z'}都是按排序顺序排列的，而忽略大小写后字符串将不相等。第二个“迭代”算法对于字符串“aab”和“abb”不正确。 - kaya3

你可以在索引检查的if语句中添加break语句，以使其更有效率。 - Reejesh PK

Answer 7

原因是它不起作用：

以“des”和“sed”为例。

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

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

将会是：如果("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, "" );

- cmonkey

Answer 8

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");

    }
}

- Isurie

Answer 9

以下是一个简洁的代码片段，可以在对两个字符串进行单次遍历以及最后对一个256元素数组进行遍历的情况下确定它们是否为变位词。该方法通过在映射数组中记录字符计数来避免对字符串中的字符进行排序和转换成/从字符串/字符数组的操作。

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始终保持常量，取决于字符集的要求。

- broadbear

Answer 10

public boolean checkAnagram(String s, String t) {
    s = s.toLowerCase();
    t = t.toLowerCase();

    // We can ignore blanks
    char[] word1 = s.replaceAll("\\s","").toCharArray();
    char[] word2 = t.replaceAll("\\s","").toCharArray();

    // Anagrams length should be the same
    if (word1.length != word2.length) {
        return false;
    }

    // Sorting arrays is pretty fast, it can be O(logn) 
    Arrays.sort(word1);
    Arrays.sort(word2);

    if (Arrays.equals(word1, word2)) {
        return true;
    }

    return false;
}

- pgardunoc