字谜检查的最佳解决方案？

Question

我正在解决一个 permutation/anagram 问题，希望就最有效的检查方法提供意见。现在，我在 Java 土地上做这件事，因此有一个库可以处理包括排序在内的所有事情。检查两个字符串是否是彼此的变位词的第一种方法是检查长度，以某种方式对它们进行排序，然后比较所述字符串的每个索引。代码如下：

private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
    return false;
}

char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();


Arrays.sort(strArr);
str = new String(strArr);

Arrays.sort(pairArr);
pair = new String(pairArr);

for(int i = 0; i<str.length(); i++){
    if(str.charAt(i) != pair.charAt(i)){
        return false;
    }
}
return true;
}

或者，我认为基于 ascii 值进行检查会更容易，并且避免检查每个可能的字符。代码如下：

private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
    return false;
}

char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();



int strValue = 0;
int pairValue = 0;

for(int i =0; i < strArr.length; i++){
    strValue+= (int) strArr[i];
    pairValue+= (int) pairArr[i];
}

if(strValue != pairValue){
    return false;
}
return true;
}

那么，哪个是更好的解决方案？我不太了解 Arrays 给我的那种类型，但是当我环顾旧的互联网时，这是更常见的答案。让我想知道我是否遗漏了什么。

Answer 1

有几种方法可以检查两个字符串是否是变位词。你的问题是，哪一个是更好的解决方案。您的第一个解决方案具有排序逻辑。排序的最坏情况复杂度为 (nlogn) 。您的第二个逻辑仅使用一个具有复杂性的循环在）。

所以在这两个中，你的第二个解决方案只有 O(n) 复杂性将是比第一个更好的解决方案。

一个可能的解决方案： </p> <pre><code>private boolean checkAnagram(String stringOne , String stringTwo){ char[] first = stringOne.toLowerCase().toCharArray(); char[] second = stringTwo.toLowerCase().toCharArray(); // if length of strings is not same if (first.length != second.length) return false; int[] counts = new int[26]; for (int i = 0; i < first.length; i++){ counts[first[i]-97]++; counts[second[i]-97]--; } for (int i = 0; i<26; i++) if (counts[i] != 0) return false; return true; }

Answer 2

最佳解决方案取决于您的 objective、代码大小、内存占用或最少的计算量。

一个非常酷的解决方案，尽可能少的代码，不是最快的 O(nlog n) 并且内存效率非常低 Java 8 :

public class Anagram {
  public static void main(String[] argc) {
    String str1 = "gody";
    String str2 = "dogy";

    boolean isAnagram =
    str1.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList())
    .equals(str2.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList()));

    System.out.println(isAnagram);
  }
}

Answer 3

我尝试了一些使用 Sets 的解决方案，并使每个解决方案运行 1000 万次以使用您的示例数组进行测试：

private static String[] input = {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"};

首先，我调用这些算法的方法：

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    for (int x = 0; x < 10000000; x++) {
        Set<String> confirmedAnagrams = new HashSet<>();
        for (int i = 0; i < (input.length / 2) + 1; i++) {
            if (!confirmedAnagrams.contains(input[i])) {
                for (int j = i + 1; j < input.length; j++) {
                        if (isAnagrams1(input[i], input[j])) {
                            confirmedAnagrams.add(input[i]);
                            confirmedAnagrams.add(input[j]);
                        }
                }
            }
        }
        output = confirmedAnagrams.toArray(new String[confirmedAnagrams.size()]);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("Total time: " + (endTime - startTime));
    System.out.println("Average time: " + ((endTime - startTime) / 10000000D));
}

然后我使用了基于字符 HashSet 的算法。我将每个单词的每个字符都添加到HashSet中，如果HashSet不是首字母单词的长度，那么它们就不是字谜。

我的算法及其运行次：

算法一：

    private static boolean isAnagrams1(String x, String y) {
    if (x.length() != y.length()) {
        return false;
    } else if (x.equals(y)) {
        return true;
    }

    Set<Character> anagramSet = new HashSet<>();
    for (int i = 0; i < x.length(); i++) {
        anagramSet.add(x.charAt(i));
        anagramSet.add(y.charAt(i));
    }

    return anagramSet.size() != x.length();
}

这有运行时间：

Total time: 6914
Average time: 6.914E-4

算法2

private static boolean isAnagrams2(String x, String y) {
    if (x.length() != y.length()) {
        return false;
    } else if (x.equals(y)) {
        return true;
    }

    Set<Character> anagramSet = new HashSet<>();
    char[] xAr = x.toCharArray();
    char[] yAr = y.toCharArray();
    for (int i = 0; i < xAr.length; i++) {
        anagramSet.add(xAr[i]);
        anagramSet.add(yAr[i]);
    }

    return anagramSet.size() != x.length();
}

运行时间为：

Total time: 8752
Average time: 8.752E-4

算法3

对于这个算法，我决定将Set发送过去，所以我每次循环只创建一次，每次测试后清除它。

    private static boolean isAnagrams3(Set<Character> anagramSet, String x, String y) {
    if (x.length() != y.length()) {
        return false;
    } else if (x.equals(y)) {
        return true;
    }

    for (int i = 0; i < x.length(); i++) {
        anagramSet.add(x.charAt(i));
        anagramSet.add(y.charAt(i));
    }

    return anagramSet.size() != x.length();
}

运行时间为：

Total time: 8251
Average time: 8.251E-4

算法4

这个算法不是我的，属于Pratik Upacharya也回答了问题，以便我比较：

    private static boolean isAnagrams4(String stringOne, String stringTwo) {
    char[] first = stringOne.toLowerCase().toCharArray();
    char[] second = stringTwo.toLowerCase().toCharArray();
    // if length of strings is not same 
    if (first.length != second.length) {
        return false;
    }
    int[] counts = new int[26];
    for (int i = 0; i < first.length; i++) {
        counts[first[i] - 97]++;
        counts[second[i] - 97]--;
    }
    for (int i = 0; i < 26; i++) {
        if (counts[i] != 0) {
            return false;
        }
    }
    return true;
}

运行时间为：

Total time: 5707
Average time: 5.707E-4

当然，这些运行每次测试的时间确实不同运行，为了进行适当的测试，需要更大的示例集，并且可能需要更多的迭代。

*已编辑，因为我在最初的方法中犯了一个错误，Pratik Upacharya's 算法似乎确实更快

Answer 4

这是一个非常简单的实现。

public boolean isAnagram(String strA, String strB) {
  // Cleaning the strings (remove white spaces and convert to lowercase)
  strA = strA.replaceAll("\s+","").toLowerCase();
  strB = strB.replaceAll("\s+","").toLowerCase();

  // Check every char of strA and removes first occurence of it in strB
  for (int i = 0; i < strA.length(); i++ ) {
    if (strB.equals("")) return false;  // strB is already empty : not an anagram
    strB = strB.replaceFirst(Pattern.quote("" + strA.charAt(i)), "");
  }

  // if strB is empty we have an anagram
  return strB.equals("");
}

最后：

System.out.println(isAnagram("William Shakespeare", "I am a weakish speller")); // true

Answer 5

//here best solution for an anagram
import java.util.*;

class Anagram{
public static void main(String arg[]){

Scanner sc =new Scanner(System.in);
String str1=sc.nextLine();
String str2=sc.nextLine();
int i,j;

boolean Flag=true;
i=str1.length();
j=str2.length();


if(i==j){
for(int m=0;m<i;m++){
    for(int n=0;n<i;n++){
        if(str1.charAt(m)==str2.charAt(n)){
           Flag=true;
           break;
          }
          else
          Flag=false;
    }
}
}
else{
Flag=false;
}

if(Flag)
System.out.println("String is Anagram");
else
System.out.println("String is not Anagram");
}
}

Answer 6

最近有个招聘人员让我解决这个问题。在研究这个问题时，我想出了一个解决两种类型的解决方案字谜问题。

问题 1：确定文本正文中是否存在字谜。

问题 2：确定文本正文中是否存在正式的字谜。在这种情况下，字谜必须与您输入的文本大小相同比较它。在前一种情况下，两个文本的大小不必相同。
一个只需要包含另一个。

我的方法如下：

设置阶段：首先创建一个字谜Class。这只会将文本转换为地图其键是有问题的字符，值包含数字输入字符的出现次数。我假设最多这需要 O(n) 时间复杂度。由于这最多需要两张地图，最坏情况下的复杂性将是 O(2n)。至少我对渐近符号的天真理解这么说。

处理阶段：您需要做的就是循环遍历两个地图中较小的一个，然后在较大的地图中查找。如果它不存在或者如果它存在但是由于出现次数不同，它无法通过变位词测试。

这是确定我们是否有字谜的循环：

    boolean looking = true;
        for (Anagram ele : smaller.values()) {
            Anagram you = larger.get(ele);
                if (you == null || you.getCount() != ele.getCount()) {
                    looking = false;
                    break;
                }
        }
        return looking;

请注意，我创建了一个 ADT 来包含正在处理的字符串。他们首先转换为地图。

这是创建 Anagram 对象的代码片段：

    private void init(String teststring2) {
        StringBuilder sb = new StringBuilder(teststring2);
        for (int i = 0; i &lt sb.length(); i++) {
            Anagram a = new AnagramImpl(sb.charAt(i));
            Anagram tmp = map.putIfAbsent(a, a);
            if (tmp != null) {
                tmp.updateCount();
            }
        }
    }

Answer 7

我的解决方案：时间复杂度 = O(n)

public static boolean isAnagram(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }

    for (int i = 0; i < str1.length(); i++) {
        char ch = str1.charAt(i);

        if (str2.indexOf(ch) == -1) 
            return false;
        else
            str2 = str2.replaceFirst(String.valueOf(ch), " ");
    }

    return true;
}

测试用例：

@Test
public void testIsPernutationTrue() {
    assertTrue(Anagram.isAnagram("abc", "cba"));
    assertTrue(Anagram.isAnagram("geeksforgeeks", "forgeeksgeeks"));
    assertTrue(Anagram.isAnagram("anagram", "margana"));
}

@Test
public void testIsPernutationFalse() {
    assertFalse(Anagram.isAnagram("abc", "caa"));
    assertFalse(Anagram.isAnagram("anagramm", "marganaa"));
}

Answer 8

这是我能够编译的更简单、更易于阅读的解决方案...

    static boolean isAnagram(String a, String b) {
    if (a.length() == b.length()){
        char[] arr1 = a.toLowerCase().toCharArray();
        char[] arr2 = b.toLowerCase().toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        if (Arrays.equals(arr1, arr2)) return true;
        else return false;
    }else return false;
}

最好的，贾斯汀

Answer 9

我想出了一个解决方案，但我什至没有使用任何 26 字符数组... 看看这个：

StringBuffer a = new StringBuffer();
        a.append(sc.next().toLowerCase());

        StringBuffer b = new StringBuffer();
        b.append(sc.next().toLowerCase());
        if(a.length() !=b.length())
        {
            System.out.println("NO");
            continue;
        }
        int o =0;
        for(int i =0;i<a.length();i++)
        {
            if(a.indexOf(String.valueOf(b.charAt(i)))<0)
            {
               System.out.println("NO");
               o=1;break; 

            }
        }
        if(o==0)
         System.out.println("Yes");

Answer 10

考虑使用 HashMap 和 Arrays.sort

    private static Map<String, String> getAnagrams(String[] data) {

    Map<String, String> anagrams = new HashMap<>();
    Map<String, String> results = new HashMap<>();

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

        char[] chars = data[i].toLowerCase().toCharArray();
        Arrays.sort(chars);

        String sorted = String.copyValueOf(chars);

        String item = anagrams.get(sorted);
        if (item != null) {
            anagrams.put(sorted, item + ", " + i);
            results.put(sorted, anagrams.get(sorted));
        } else {
            anagrams.put(sorted, String.valueOf(i));
        }
    }

    return results;
}

我喜欢它，因为你只遍历数组一次。

Answer 11

使用原始数据类型的解决方案。

boolean isAnagram(char input1[], char input2[]) {
    int bitFlip = 32;

    if(input2.length != input1.length){return false;}

    boolean found = false;
    for (int x = 0; x < input1.length; x++) {
        found = false;
        for (int y = 0; y < input2.length; y++) {
             if (!found && ((input1[x] | bitFlip)) ==
             ( (input2[y] | bitFlip))) {
                found = true;
                input2[y] = 0;
            }
        }
        if (!found) {
            break;
        }
    }
    return found ;
}

此方法不依赖于任何排序实用程序。它所做的是通过迭代找到值，在找到它之后，它将其设置为零以避免输入重复字符，如 "pool" 和 "loop" 有两个字母 "o"。

它也忽略大小写而不依赖于 toLowerCase() 通过翻转位，因为如果第 6 位（十进制中的 32）为 1，则为小写字母，如果为零则为大写字母。

它是直接字节操作，因此它会像图像处理中使用的那样执行得更好。也许缺点是 O(n^2).

此解决方案已在 hackerrank

中进行测试

Answer 12

简单的 kotlin 解决方案

fun IsAnagram(s1: String, s2: String): Boolean {
    return s1.groupBy { it } == s2.groupBy { it }
}

GroupBy的渐近时间复杂度为O(n)，上面的时间复杂度为O(n)

字谜检查的最佳解决方案？

Best solution for an anagram check?

java

compare

anagram