Как найти анаграмму для 2 строк

Question

Как найти анаграмму для 2 строк

Я написал программу на Java, чтобы найти Anagram для 2 строк.

Для справки: две строки являются анаграммами, если они написаны одинаковыми точными буквами, игнорируя пробел, знаки препинания и заглавные буквы. Каждая буква должна иметь одинаковое количество в обеих строках. Например, Армия и Мэри являются анаграммами друг друга.

Программа:

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

Здесь, если вы видите, что все символы добавлены в массив, но при сравнении со строкой, он показывает выходные данные, поскольку они не являются анаграммами друг друга.

Пожалуйста, помогите мне найти решение для этого.

Спасибо,

1

java string anagram

Источник

user2987894 25 ноя '16 в 12:32

7 ответов

Решение

Вы можете посчитать количество букв в обеих строках. Если обе строки имеют одинаковое количество букв, они являются анаграммами.

Вы можете использовать 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']++, В этой строке кода используются интересные свойства типа char Java, который является специальным примитивным числовым типом, так что можно использовать математические операции над ним.

Особенно:

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

Таким образом, это выражение может быть использовано для присвоения индекса букве, начинающейся с 0 для A и заканчивающейся 25 для Z.

3

Источник

user1803853 25 ноя '16 в 12:53

Ваши выводы говорят сами за себя: значение массива [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");
            }

        }

2

Источник

user6232539 25 ноя '16 в 12:53

Мой ответ очень похож на ответ 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 создает карту с каждым уникальным символом, сопоставленным с его количеством в данной строке. Это может быть немного менее производительным, чем у Марина, но все же O(n),

2

Источник

user2437892 25 ноя '16 в 13:42

В этом коде я преобразовал свою строку в массив символов, используя код:String.toCharArray() внутри функции с именем toSort() и отсортированы слова в строке. Затем внутри метода Isanagram() я проверил, анаграмма это или нет. Для этого сначала я должен убедиться, что отсортированные строки имеют одинаковую длину или нет, после того как я сравнил каждый символ в одной строке с другим. Вот полный код, попробуйте разложить каждый метод и изучить.

   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

0

Источник

user9367958 01 мар '18 в 05:37

Вот как вы можете сделать это, отсортировав массивы:

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

0

Источник

user6774829 25 ноя '16 в 12:54

Используйте.split("(?!^)") На вашей строке, чтобы сделать его массивом строк. Далее сортируйте массивы и сравнивайте их. Это лучший вариант для меня тоже.

0

Источник

user5706691 25 ноя '16 в 12:54

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

    }

}

0

Источник

user12917561 22 апр '20 в 13:38

Другие вопросы по тегам java string anagram

user1155916 25 ноя '16 в 12:44 2016-11-25 12:44 · Accepted Answer · 2016-11-25 12:44

Я думаю, что ваше решение будет работать только для слов с уникальными символами, а временная сложность будет O(n^2) (где n - длина строки).

Тем не менее, есть лучшее решение для такой проблемы:

принимать String.toCharArray() значение для каждой строки
Сортировать эти массивы
Если эти массивы равны, то ваши слова анаграммы