Анаграммы - как пройти два теста ниже?

Question

Вот мой код того, являются ли две строки анаграммами или нет

static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    a = a.toLowerCase();
    b = b.toLowerCase();
    int m1=0;
    for(int i=0;i<a.length();i++){
        m1 += (int)a.charAt(i);
        m1 -= (int)b.charAt(i);

    }
        return m1==0;
}

Мой код не выполняется для двух тестовых случаев

• case 1: String a="xyzw"; и String b="xyxy";
• дело 2: String a="bbcc"; и String b="dabc";

Может кто-нибудь помочь мне передать два вышеупомянутых дела?

Answer 1

Вы добавляете значения ascii символов в заданные строки и сравниваете их, что не всегда дает правильные результаты.Подумайте об этом:

String a="acd" и String b="ccb"

оба дадут вам сумму 296, но это не анаграммы.

Вы можете подсчитать вхождениясимволы в строке и сравнить их.В приведенном выше примере он даст вам {"a": 1, "c": 1, "d": 1} и {"c": 2, "b": 1}.

Кроме того,Вы можете связать простое число с каждым из набора символов [az], где «a» соответствует 2, «b» соответствует 3, «c» соответствует 5 и т. д.

Далее вы можете вычислить умножениеиз простых чисел, связанных с символами в данной строке.Умножение следует правилам ассоциативности (x y = y x).

Пример:

abc -> 2 * 3 * 5 = 30

cba -> 5 * 3 * 2 = 30

Примечание: Если размер строки огромен, это может быть не лучшим подходом, поскольку вы можете столкнуться с проблемами переполнения.

Answer 2

Ознакомьтесь со следующими методами:

/**
 * Java program - String Anagram Example.
 * This program checks if two Strings are anagrams or not
 */
public class AnagramCheck {

/*
 * One way to find if two Strings are anagram in Java. This method
 * assumes both arguments are not null and in lowercase.
 *
 * @return true, if both String are anagram
 */
public static boolean isAnagram(String word, String anagram){       
    if(word.length() != anagram.length()){
        return false;
    }

    char[] chars = word.toCharArray();

    for(char c : chars){
        int index = anagram.indexOf(c);
        if(index != -1){
            anagram = anagram.substring(0,index) + anagram.substring(index +1, anagram.length());
        }else{
            return false;
        }           
    }

    return anagram.isEmpty();
}

/*
 * Another way to check if two Strings are anagram or not in Java
 * This method assumes that both word and anagram are not null and lowercase
 * @return true, if both Strings are anagram.
 */
public static boolean iAnagram(String word, String anagram){
    char[] charFromWord = word.toCharArray();
    char[] charFromAnagram = anagram.toCharArray();       
    Arrays.sort(charFromWord);
    Arrays.sort(charFromAnagram);

    return Arrays.equals(charFromWord, charFromAnagram);
}


public static boolean checkAnagram(String first, String second){
    char[] characters = first.toCharArray();
    StringBuilder sbSecond = new StringBuilder(second);

    for(char ch : characters){
        int index = sbSecond.indexOf("" + ch);
        if(index != -1){
            sbSecond.deleteCharAt(index);
        }else{
            return false;
        }
    }

    return sbSecond.length()==0 ? true : false;
}

}

Answer 3

Попробуйте это.Он будет выполнен в O (word.length).

public boolean checkForAnagram(String str1, String str2) {
    if (str1 == null || str2 == null || str1.length() != str2.length()) {
        return false;
    }
    return Arrays.equals(getCharFrequencyTable(str1), getCharFrequencyTable(str2));
}

private int[] getCharFrequencyTable(String str) {
    int[] frequencyTable = new int[256]; //I am using array instead of hashmap to make you realize that its a constant time operation.
    char[] charArrayOfStr = str.toLowerCase().toCharArray();
    for(char c : charArrayOfStr) {
        frequencyTable[c] = frequencyTable[c]+1;
    }
    return frequencyTable;
}

Answer 4

Добавление символьных значений является склонной к ошибкам логикой, поскольку A+C и B+B генерируют одинаковое число.Лучшим вариантом в этом случае является использование массивов.Посмотрите на код ниже -

static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    a = a.toLowerCase();
    b = b.toLowerCase();

    char[] charA = a.toCharArray();
    Arrays.sort(charA);

    char[] charB = b.toCharArray();
    Arrays.sort(charB);

    return Arrays.equals(charA, charB);
}

Это должно дать вам то, что вы хотите.

Answer 5

Попробуйте это:

import java.io.*; 

class GFG{ 

    /* function to check whether two strings are  
    anagram of each other */
    static boolean areAnagram(char[] str1, char[] str2) 
    { 
        // Get lenghts of both strings 
        int n1 = str1.length; 
        int n2 = str2.length; 

        // If length of both strings is not same, 
        // then they cannot be anagram 
        if (n1 != n2) 
            return false; 

        // Sort both strings 
        quickSort(str1, 0, n1 - 1); 
        quickSort(str2, 0, n2 - 1); 

        // Compare sorted strings 
        for (int i = 0; i < n1;  i++) 
            if (str1[i] != str2[i]) 
                return false; 

        return true; 
    } 

    // Following functions (exchange and partition  
    // are needed for quickSort) 
    static void exchange(char A[],int a, int b) 
    { 
        char temp; 
        temp = A[a]; 
        A[a]   = A[b]; 
        A[b]   = temp; 
    } 

    static int partition(char A[], int si, int ei) 
    { 
        char x = A[ei]; 
        int i = (si - 1); 
        int j; 

        for (j = si; j <= ei - 1; j++) 
        { 
            if(A[j] <= x) 
            { 
                i++; 
                exchange(A, i, j); 
            } 
        } 
        exchange (A, i+1 , ei); 
        return (i + 1); 
    } 

    /* Implementation of Quick Sort 
    A[] --> Array to be sorted 
    si  --> Starting index 
    ei  --> Ending index 
    */
    static void quickSort(char A[], int si, int ei) 
    { 
        int pi;    /* Partitioning index */
        if(si < ei) 
        { 
            pi = partition(A, si, ei); 
            quickSort(A, si, pi - 1); 
            quickSort(A, pi + 1, ei); 
        } 
    } 

    /* Driver program to test to print printDups*/
    public static void main(String args[]) 
    { 
        char str1[] = {'t','e','s','t'}; 
        char str2[] = {'t','t','e','w'}; 
        if (areAnagram(str1, str2)) 
            System.out.println("The two strings are"+ 
                             " anagram of each other"); 
        else
            System.out.println("The two strings are not"+ 
                               " anagram of each other"); 
    } 
} 

Answer 6

Я думаю, что ваш код не работает, потому что вы суммируете код символов, но, возможно, ответ равен нулю, но они не равны, например: "ad" "bc"
лучший способ сделать этосортировать символы строк, если они имеют одинаковую длину массива и одинаковый порядок, поэтому две строки являются анаграммами.

static boolean isAnagram(String str1, String str2) {
    int[] str1Chars = str1.toLowerCase().chars().sorted().toArray();
    int[] str2Chars = str2.toLowerCase().chars().sorted().toArray();
    return Arrays.equals(str1Chars, str2Chars);
}

Надеюсь, это поможет вам.(это немного сложно, потому что я использую поток для создания и сортировки массива символов)

Answer 7

Реализация неверна.Хотя пара анаграмм всегда будет иметь одинаковую длину и одинаковую сумму символов, это не является достаточным условием.Есть много пар строк, которые имеют одинаковую длину и одинаковую сумму символов и не являются анаграммами.Например, "ad" и "bc".

Лучшая реализация подсчитала бы количество раз, которое каждый символ появляется в каждой строке, и сравнила бы их.Например:

public static boolean isAnagram(String a, String b) {
    return charCounts(a).equals(charCounts(b));
}

private static Map<Integer, Long> charCounts(String s) {
    return s.chars()
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

Answer 8

static boolean isAnagram(String a, String b) {
        if (a.length() != b.length())
            return false;
        a = a.toLowerCase();
        b = b.toLowerCase();
        HashMap<Integer, Integer> m1 = new HashMap<>(); // Key is ascii number, Value is count. For String a
        HashMap<Integer, Integer> m2 = new HashMap<>(); // Key is ascii number, Value is count. For String b
        for (int i = 0; i < a.length(); i++) {
            int an = (int) (a.charAt(i));
            int bn = (int) (b.charAt(i));
            // Add 1 to current ascii number. String a.
            if (m1.containsKey(an)) {
                m1.put(an, m1.get(an) + 1);
            }else {
                m1.put(an, 1);
            }
            // Add 1 to current ascii number. String b.
            if (m2.containsKey(bn)) {
                m2.put(bn, m2.get(bn) + 1);
            }else {
                m2.put(bn, 1);
            }
        }

        //Check both count equals().
        return m1.equals(m2);
    }

вы должны проверять каждые буквы.Если (ascii of a [0] == ascii of b [0] + 1) и (ascii of a [1] == ascii of b [1] - 1) он вернет true, потому что 1 - 1 равно нулю.Извините за очень очень сложный код.