如何找到 2 个字符串的字谜

Question

我编写了一个 Java 程序来查找 2 个字符串的 Anagram。

供参考：如果两个字符串使用完全相同的字母书写，忽略 space、标点符号和大写，则它们是变位词。每个字母在两个字符串中的计数应该相同。例如，Army 和 Mary 是彼此的变位词。

节目：

package practice;

import java.util.ArrayList;
import java.util.List;

public class Anagram_String {

    public static void main(String[] args) {

        String s1="mary";
        String s2="army";
        int k=0;
        List<String> matchedChar= new ArrayList<String>();
        String charmatch="";

        char[] ch1= s1.toLowerCase().toCharArray();
        char[] ch2= s2.toLowerCase().toCharArray();

        if(s1.length()==s2.length())
        {

            for(int i=0;i<s1.length();i++)
            {
                for(int j=0;j<s2.length();j++)
                {
                    if(ch1[i]==ch2[j])
                    {
                        k++;
                        charmatch=String.valueOf(ch1[i]);
                        System.out.println(charmatch);
                        matchedChar.add(charmatch);
                        System.out.println("Arraylist value is "+matchedChar.toString());
                        System.out.println(matchedChar.size());
                    }
                }

                k=0;
            }

            String arrayValue=matchedChar.toString();
            System.out.println("Array value is "+arrayValue);

            if(arrayValue.contains(s2)){

                System.out.println("String 1 and String 2 are anagrams of each other");

            }
            else
            {
                System.out.println("String 1 and String 2 are not anagrams of each other");
            }

        }

    }

}

输出：

m
Arraylist value is [m]    
1  
a  
Arraylist value is [m, a]    
2   
r   
Arraylist value is [m, a, r]    
3  
y   
Arraylist value is [m, a, r, y]   
4   
Array value is [m, a, r, y]  
String 1 and String 2 are not anagrams of each other

在这里，如果您看到所有字符都已添加到数组列表中，但与字符串进行比较时，它显示的是输出，因为它们不是彼此的变位词。

请帮我找到解决办法。

谢谢，

Answer 1

我认为您的解决方案仅适用于具有唯一字符的单词，时间复杂度为 O(n^2)（其中 n - 是字符串的长度).

但是，对于这样的问题有更好的解决方案：

为每个字符串取String.toCharArray()值
对这些数组进行排序
如果这些数组相等，那么你的话就是字谜

Answer 2

您可以计算两个字符串中的字母数。如果两个字符串具有相同数量的字母，则它们是变位词。

您可以使用 int[] 来存储字母数。

public static boolean anagrams(String a, String b) {
    int[] letters = new int[26];

    // Convert to upper case because the test is case insensitive
    a = a.toUpperCase();  
    b = b.toUpperCase();
    for (int i = 0; i < a.length(); i++) {
        char ch = a.charAt(i);
        if (ch < 'A' || ch > 'Z') {
            continue; // Skip non letters
        }
        letters[ch - 'A']++;   // Increment number of the current letter
    }
    for (int i = 0; i < b.length(); i++) {
        char ch = b.charAt(i);
        if (ch < 'A' || ch > 'Z') {
            continue; // Skip non letters
        }
        letters[ch - 'A']--;   // Decrement number of the current letter

    }
    for (int i = 0; i < letters.length; i++) {
        if (letters[i] != 0) {
            // If there are more or less of this letter 
            // in the first string it is not an anagram
            return false;
        }
    }
    return true;
}

请注意，此算法的复杂度为 O(n)，其中 n 是每个字符串的字母数。对字符串进行排序至少需要 O(n log(n))

根据 AxelH 的评论，可以创建一个外部方法来循环，如下所示。

private void countLetters(int[] letters, String str, int incrementFactor) {
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (ch < 'A' || ch > 'Z') {
            continue; // Skip non letters
        }
        letters[ch - 'A'] += incrementFactor; 
    }
}

public static boolean anagrams(String a, String b) {
    int[] letters = new int[26];

    countLetters(letters, a.toUpperCase(), 1);   // Note the +1
    countLetters(letters, b.toUpperCase(), -1);  // Note the -1

    for (int i = 0; i < letters.length; i++) {
        if (letters[i] != 0) {
            // If there are more or less of this letter 
            // in the first string it is not an anagram
            return false;
        }
    }
    return true;
}

在我看来，这是一种更具可读性和优雅的方式。谢谢 AxelH。

注意前面的代码中有letters[ch - 'A']++这样的表达式。这行代码使用了 java 的 char 类型的有趣属性，这是一种特殊的原始数字类型，因此可以对其进行数学运算。

特别是：

'A' - 'A' --> 0
'B' - 'A' --> 1
'C' - 'A' --> 2
'D' - 'A' --> 3
...
'Z' - 'A' --> 25

因此该表达式可用于为字母提供索引，从 A 的 0 到 Z 的 25。

Answer 3

您的输出说明了一切：数组值为 [m, a, r, y]

如上所述，我也会创建数组并对它们进行排序，但这里是您可能正在寻找的解决方案：

        String s1="mary";
        String s2="army";
        List<String> matchedChar= new ArrayList<String>();
        String charmatch="";

        char[] ch1= s1.toLowerCase().toCharArray();
        char[] ch2= s2.toLowerCase().toCharArray();

        if(s1.length()==s2.length())
        {

            for(int i=0;i<s1.length();i++)
            {
                for(int j=0;j<s2.length();j++)
                {
                    if(ch1[i]==ch2[j])
                    {
                        charmatch=String.valueOf(ch1[i]);
                        System.out.println(charmatch);
                        matchedChar.add(charmatch);
                        System.out.println("Arraylist value is "+matchedChar.toString());
                        System.out.println(matchedChar.size());
                    }
                }
            }

            String arrayValue="";
            for (String s : matchedChar){
                arrayValue = arrayValue + s;
            }
            System.out.println("Array value is "+arrayValue);
            System.out.println("s1 value is "+s1);

            if(arrayValue.equals(s1)){

                System.out.println("String 1 and String 2 are anagrams of each other");

            }
            else
            {
                System.out.println("String 1 and String 2 are not anagrams of each other");
            }

        }

Answer 4

这是通过对数组进行排序来实现的：

public static void main(String[] args) {
    System.out.println(isAnagram("mary", "army"));
}

public static boolean isAnagram(String s1, String s2){
    char[] c1 = s1.toLowerCase().toCharArray();
    char[] c2 = s2.toLowerCase().toCharArray();
    Arrays.sort(c1);
    Arrays.sort(c2);

    boolean anagram = false;
    if(Arrays.equals(c1, c2)){anagram = true;}

    return anagram;
}

Answer 5

对字符串使用 .split("(?!^)") 使其成为字符串数组。接下来对数组进行排序并进行比较。这对我来说也是最好的选择。

Answer 6

我的回答与 Marine 的非常相似，但采用了更高层次的方法 Java 8 个流，使代码更加简洁和可读：

public class Application {

public boolean isAnagramsEqual(String str1, String str2) {
    Map<Character, Long> count = countChars(str1);
    Map<Character, Long> count2 = countChars(str2);

    return count.equals(count2);
}

private Map<Character, Long> countChars(String str) {
    return str.toLowerCase()                 
            .chars().mapToObj(ch -> (char) ch)      //convert into stream of Characters
            .filter(Character::isLetterOrDigit)     //filter out not-needed chars
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 
}}

方法countChars 创建一个映射，每个唯一字符都映射到它在给定字符串中的计数。它的性能可能比 Marine 的性能稍差，但仍然是 O(n).

Answer 7

在这段代码中，我在名为 toSort() 的函数中使用代码 :String.toCharArray() 将我的字符串转换为 char 数组，并对字符串中的单词进行排序。然后在 Isanagram() 方法中我检查它是否是 anagram。首先，在将一个字符串中的每个字符与另一个字符串进行比较后，我必须确保排序后的字符串是否具有相同的长度。下面是完整代码尝试分解各个方法学习

   import java.util.Scanner;

public class StANaEx1 {



String toSort(String s5){
    int i,j;
    char temp;
    char ch1[] = s5.toCharArray();
    int len = ch1.length;
    for(i=0;i<len;i++){
        for(j=i+1;j<len;j++){
            if(ch1[i]>ch1[j]){
                temp = ch1[i];
                ch1[i] = ch1[j];
                ch1[j] = temp;
            }
        }
    }
    String s6 = new String(ch1);
return s6;
}



void isAnagram(String s9,String s10){
    int i,len1,len2,flag=0;
    System.out.println("s9 : "+s9);
    System.out.println("s10 : "+s10);
    System.out.println("");
    s9 = s9.trim();                     //To remove white spaces again no need.I used because my compiler didn't recognize my replace() method in main() method. 
    s10 = s10.trim();
    len1 = s9.length();
    len2 = s10.length();
    System.out.println("len1 : "+len1);     //To check the length of the given strings without white spaces.
    System.out.println("len2 : "+len2);
    System.out.println("");
    for(i=0;i<len1;i++){
        System.out.println("s9["+i+"] : "+s9.charAt(i));        //Error checking.
    }
    System.out.println("");
    for(i=0;i<len2;i++){
        System.out.println("s10["+i+"] : "+s10.charAt(i));
    }
    System.out.println("");
    if(len1!=len2){
        System.out.println("Not Anagram string length different");
    }
    else{
        for(i=0;i<len1;i++){                    //Since string lengths are same len1 = len2.
            if(s9.charAt(i)!=s10.charAt(i)){
                flag=1;
                break;
            }
        }
        if(flag==0){
            System.out.println("Anagram");
        }
        else{
            System.out.println("Not Anagram");
        }
    }
}




public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    StANaEx1 ob1 = new StANaEx1();
    System.out.println("-----Anagram checking-----");
    System.out.println("");
    System.out.println("Enter the 1st String: ");
    System.out.println("");
    String s1 = sc.nextLine();
    s1 = s1.replace("//s", "");         //This is to remove white spaces.
    String s3 = s1.toLowerCase();       //Change the input string to lower case in order to make sorting easy.
    System.out.println("");
    System.out.println("Enter the next String: ");
    String s2 = sc.nextLine();
    s2 = s2.replace("//s", "");
    String s4 = s2.toLowerCase();
    System.out.println("");

    String s7 = ob1.toSort(s3);
    String s8 = ob1.toSort(s4);

    ob1.isAnagram(s7,s8);

    sc.close();

}
}

输出

   -----Anagram checking-----

Enter the 1st String: 

Mary

Enter the next String: 
army

s9 : amry
s10 : amry

len1 : 4
len2 : 4

s9[0] : a
s9[1] : m
s9[2] : r
s9[3] : y

s10[0] : a
s10[1] : m
s10[2] : r
s10[3] : y

Anagram

输出 2

-----Anagram checking-----

Enter the 1st String: 

Sniper

Enter the next String: 
kill

s9 : einprs
s10 : ikll

len1 : 6
len2 : 4

s9[0] : e
s9[1] : i
s9[2] : n
s9[3] : p
s9[4] : r
s9[5] : s

s10[0] : i
s10[1] : k
s10[2] : l
s10[3] : l

Not Anagram string length different

Answer 8

import java.util.Arrays;

public class AnagramString {

    public static void main(String[] args) {

        String str1="Keep";
        String str2="peek";

        //convert the string into the array with lower casing its character 

        char arrstr1[]=str1.toLowerCase().toCharArray();  
        char arrstr2[]=str2.toLowerCase().toCharArray(); 

        //sort the array of character by acending order

        Arrays.sort(arrstr1);
        Arrays.sort(arrstr2);

        //set true boolean value to the status

        boolean status=true;

        //comparing the char array

         status = Arrays.equals(arrstr1, arrstr2);//here we get true value if they are containing the same character

        System.out.println(Arrays.toString(arrstr1));
        System.out.println(Arrays.toString(arrstr2));

        if(arrstr1.length==arrstr2.length  && status) {
            System.out.println("2 string are anagram");
        }else {
            System.out.println("2 string are not anagram");
        }

    }

}

如何找到 2 个字符串的字谜

How to find anagram for 2 Strings

java

string

anagram