java - 在 Java 中查找字谜

Question

我遇到了一个问题。我有一个字符串数组，它由 String[]={"eat", "tea", "tan", "ate", "nat", "bat"} 组成现在，我应该将那些具有相同字母的单词分开并组成一个组。 eat,tea,ate他们在每个单词中都有相同的字母，所以这是一组。第 2 组应该是 tan,nat Group3 应该是 bat .所以我必须制作一个列表来存储这些组。

我的方法:

为了解决这个问题，我首先找出每个字母的 ascii 值，然后将这些 ascii 值加到一个单词上。喜欢eat找出 e,a,t 的 ascii 值并添加它们。我采用这种方法是因为如果字母在单词中重复，那么它们必须具有相同的 ascii 总和。之后，我将它们归为相同的 Ascii 总和，找出哪些单词具有这些总和，然后它们属于同一组。

我的进步我找出 ascii 和并将它们放入 HashMap 中。但是后来我无法对相同的值进行分组。由于我未能对 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);

    }

另一种方法我在 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;
    }
}

该程序将适用于诸如此类的小规模事物，但请考虑以下输入数据:

{“一个”，“@!”

这些字符串的和都是97。

由于您使用 ASCII 值来查找变位词，因此您可能会遇到这样的情况。在您开始弄乱小写字母和大写字母之前，这并不是一个特别紧迫的问题。只需 String.ToUpperCase() 并将符号映射到巨大的数字即可轻松解决此问题，您就可以开始了。