Нахождение анаграмм в яве

Question

Я застрял на проблеме.У меня есть массив строк, который состоит из String[]={"eat", "tea", "tan", "ate", "nat", "bat"} Теперь я должен отделить те слова, которые имеют одинаковые буквы на нем, и создать группу.eat,tea,ate у них одинаковые буквы в каждом слове, так что это группа.Группа 2 должна быть tan,nat, а Группа3 должна быть bat.Поэтому я должен составить список для хранения этих групп.

Мой подход:

Чтобы решить эту проблему, я сначала выясняю значения ascii для каждой буквы, а затем добавляю эти значения ascii для слова.Как и eat, найдите значения ascii e,a,t и добавьте их.Я использую этот подход, потому что если буквы повторяются в словах, то они должны иметь одинаковую сумму ascii.После этого я группирую те же суммы Ascii и выясняю, какие слова имеют эти суммы, тогда они принадлежат к той же группе.

Мой прогресс Я нахожу суммы ascii и помещаю их в хэш-карту.Но тогда я не смог сгруппировать одинаковые значения.Поскольку мне не удалось сгруппировать значения ascii, я не могу найти слова. Я понятия не имею, как поступить.

Я также следую за этими постами

post1 post2

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

Мой код:

public List<List<String>> groupAnagrams(String[] strs) {
    ArrayList<Character>indivistr=new ArrayList<>();
    ArrayList<Integer>dup=new ArrayList<>();
    HashMap<Integer,Integer>mappingvalues=new HashMap<>();
    for(int i=0;i<strs.length;i++){
        int len=strs[i].length();
        int sum=0;
        for(int j=0;j<len;j++){
            indivistr.add(strs[i].charAt(j));
            int ascii=(int)strs[i].charAt(j);
            sum=sum+ascii;

        }
        mappingvalues.put(i,sum);

    }

}

Oneбольше подхода Я передаю ключи карты в Arraylist и значения карты в ArrayList.Примерно так:

ArrayList<Integer>key_con=new ArrayList< (mappingvalues.keySet()); ArrayList<Integer>val_con=new ArrayList<>(mappingvalues.values());

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

for(int k=0;k<val_con.size();k++){
        for(int k1=k+1;k1<val_con.size();k1++){
            if(val_con.get(k).equals(val_con.get(k1))){
                dup.add(val_con.get(k1));
            }
        }

Теперь, если я напечатаю dup, вывод будет [314, 314, 314, 323], что частично правильно.Должно быть 314,314,314,323,323,311

Answer 1

Это должно помочь вам начать работу.

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

public class Main {

    public static void main(String args[]) throws Exception {

        String[] words ={"eat", "tea", "tan", "ate", "nat", "bat"};

        for(List<String> list : groupAnagrams(words))
            System.out.println(list);

    }

    public static List<ArrayList<String>> groupAnagrams(String[] words) {

        List<ArrayList<String>> wordGroups = new ArrayList<ArrayList<String>>();
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();

        for(String word : words) {

            int sum = 0;
            for(char c : word.toCharArray())
                sum += c;
            if(map.containsKey(sum))
                map.get(sum).add(word);
            else {
                ArrayList<String> list = new ArrayList<String>();
                list.add(word);
                map.put(sum, list);
            }

        }

        for(ArrayList<String> list : map.values())
            wordGroups.add(list);

        return wordGroups;
    }
}

Эта программа будет работать для мелкомасштабных задач, таких как эта, но учитывайте следующие входные данные:

{"a", "@!"}

Сумма этих строк равна 97.

Поскольку вы используете значения ASCII для поиска анаграмм, вы можете столкнуться с таким случаем, как этот.Это не особенно актуально, пока вы не начнете возиться со строчными буквами и заглавными буквами.Это легко исправить, просто набрав String.ToUpperCase() и сопоставив символы с огромными числами, и все готово.

Answer 2

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

class Anagram {
   String s;
   String sorted;
}

Затем я сопоставлю входные данные с моим списком Anagram:

List<Anagram> collect = Arrays.stream(strs)
            .map(a -> new Anagram(a, Arrays.stream(a.split(""))
                    .sorted()
                    .reduce(String::concat).get()))
            .collect(Collectors.toList());

Затем я просто группирую полученный список по отсортированной строке:

 Map<String, List<Anagram>> groupBy = collect
             .stream()
             .collect(Collectors.groupingBy(Anagram::getSorted));

Теперь у вас есть списки с сгруппированными анаграммами, просто извлеките из них исходную строку:

List<List<String>> result = new ArrayList<>();

for(List<Anagram> list : collect1.values()) {
     List<String> myList = list.stream().map(Anagram::getS).collect(Collectors.toList());
     result.add(myList);
}

Answer 3

Основываясь на подходе asci, я создал рабочий код

public static void main(String[] args) {
        String[] values ={"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<Integer, List<String>> resultMap = new HashMap<Integer, List<String>>();
        for (String value : values) {
            char[] caharacters = value.toLowerCase().toCharArray();
            int asciSum = 0;
            for (char character : caharacters) {
                asciSum = asciSum + (int)character;
            }
            System.out.println(asciSum);
            if(resultMap.containsKey(asciSum)) {
                resultMap.get(asciSum).add(value);
            }else {
                List<String> list = new ArrayList<String>();
                list.add(value);
                resultMap.put(asciSum, list);
            }
        }
        System.out.println(resultMap);
    }

Это даст результат

{323=[tan, nat], 311=[bat], 314=[eat, tea, ate]}

, но если мы встретим символы diff с такой же суммой значений asci, как 10+11 = 20 + 1, приведенный ниже код будет работать там, где на основе отсортированной строки мы создаем карту результатов

public static void main(String[] args) {
        String[] values ={"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> resultMap = new HashMap<String, List<String>>();
        for (String value : values) {
            char[] caharacters = value.toLowerCase().toCharArray();
            Arrays.sort(caharacters);
            String sortedValue = new String(caharacters);
            System.out.println(sortedValue);
            if(resultMap.containsKey(sortedValue)) {
                resultMap.get(sortedValue).add(value);
            }else {
                List<String> list = new ArrayList<String>();
                list.add(value);
                resultMap.put(sortedValue, list);
            }
        }
        System.out.println(resultMap);
    }

. Это вернет

{aet=[eat, tea, ate], abt=[bat], ant=[tan, nat]}

Я исправил предоставленные комментарии и правки.