Je suis resté coincé sur un problème. J'ai un tableau de chaînes composé de String [] = {"eat", "tea", "tan", "ate", "nat", "bat"} Maintenant, je devrais séparer ces mots qui ont la même lettre dessus et forment un groupe. manger, thé, manger ils ont la même lettre dans chaque mot donc c'est un groupe. Le groupe 2 doit être tan, nat et le groupe 3 doit être bat . Je dois donc faire une liste de liste pour stocker ces groupes.
Mon approche:
Pour résoudre ce problème, je trouve d'abord les valeurs ascii de chaque lettre, puis j'ajoute ces valeurs ascii pour un mot. Comme eat , découvrez les valeurs ascii de e, a, t et ajoutez-les. J'adopte cette approche parce que si les lettres sont répétées dans les mots, elles doivent avoir la même somme ascii. Après cela, je les regroupe les mêmes sommes Ascii et découvre quels mots ont ces sommes, puis ils appartiennent au même groupe.
Ma progression Je découvre les sommes ascii et les mets dans un hashmap. Mais alors je ne pouvais pas regrouper les mêmes valeurs. Comme je n'ai pas réussi à regrouper les valeurs ascii, je ne peux pas trouver les mots, je ne sais pas comment procéder.
Je suis également ce message
Mais là approche et mon approche n'est pas la même. Les questions sont également différentes des miennes. Je parle ici d'une approche différente qui dépend des valeurs ASCII.
Mon code:
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));
}
}
} p>
Encore une approche Je transfère les clés de carte dans une Arraylist et mappe les valeurs dans une ArrayList. Quelque chose comme ça,
ArrayList
Puis en utilisant deux boucles et mettez les mêmes valeurs dans une autre liste.
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);
}
Maintenant, si j'imprime dup, la sortie sera [314, 314, 314, 323] , ce qui est partiellement correct. Ce devrait être 314,314,314,323,323,311
3 Réponses :
Basé sur l'approche asci, j'ai créé un code fonctionnel
{aet=[eat, tea, ate], abt=[bat], ant=[tan, nat]}
Cela donnera un résultat
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);
}
mais si nous rencontrons des caractères différents avec la même somme de valeur asci comme 10 + 11 = 20 + 1 le code ci-dessous fonctionnera là où, en fonction de la chaîne triée, nous créons la carte de résultats
{323=[tan, nat], 311=[bat], 314=[eat, tea, ate]}
Cela retournera
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);
}
J'ai a corrigé les commentaires et les modifications fournis.
l'approche avec certains est fausse, vous n'obtiendrez pas le résultat correct de certaines entrées. Si vous obtenez une somme de 200, comment faites-vous maintenant mon ajout de 100 + 100, ou en ajoutant 90 + 110?
Cela devrait vous aider à démarrer.
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;
}
}
Ce programme fonctionnera pour des choses à petite échelle comme celle-ci, mais considérez les données d'entrée suivantes:
{"a", "@!"}
La somme de ces chaînes est 97.
Puisque vous utilisez des valeurs ASCII pour trouver des anagrammes, vous risquez de rencontrer un cas comme celui-ci. Ce n'est pas une question particulièrement urgente jusqu'à ce que vous commenciez à jouer avec des lettres minuscules et des majuscules. Une solution simple pour cela est juste un String.ToUpperCase () et associez les symboles à des nombres énormes et vous êtes prêt à partir.
Il avait donné que tous les mots en minuscules.
@Encipher absolument. J'ai créé un ArrayList de ArrayLists pour les groupes à stocker. J'ai ensuite créé un HashMap qui a pris un Integer (la somme de la chaîne) comme clé et un ArrayList de String qui était le groupe. J'ai ensuite parcouru tous les mots de mon tableau String et ajouté chaque caractère dans une variable de somme. J'ai ensuite vérifié si mon HashMap contenait déjà la somme. S'il l'a ajouté au groupe spécifié. Sinon, créez un nouveau groupe avec la somme des clés. J'ai ensuite ajouté toutes les valeurs HashMap à une ArrayList qui est facultative. Si j'ai besoin de développer davantage sur un domaine spécifique, faites-le moi savoir.
Voici mon idée, d'abord je créerais une classe qui stockera la chaîne d'origine et sa version triée:
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);
}
Ensuite, je mappe l'entrée à ma liste de Anagram code>:
Map<String, List<Anagram>> groupBy = collect
.stream()
.collect(Collectors.groupingBy(Anagram::getSorted));
Ensuite, je regroupe simplement la liste obtenue par chaîne triée:
List<Anagram> collect = Arrays.stream(strs)
.map(a -> new Anagram(a, Arrays.stream(a.split(""))
.sorted()
.reduce(String::concat).get()))
.collect(Collectors.toList());
Vous avez maintenant les listes avec des anagrammes groupées, il suffit d'en extraire la chaîne d'origine:
class Anagram {
String s;
String sorted;
}
"Une discussion saine est toujours la bienvenue." <- Non, ce n'est pas un site de chat. C'est un site de questions et réponses. Et j'ai du mal à voir une question ici.
avez-vous essayé d'utiliser une variable supplémentaire. Donc, vous mettez le mot initial à cette variable. Maintenant, parcourez tous les mots. Pour chaque mot, pour chaque lettre que vous examinez si elle est dans votre mot enregistré - si vous obtenez un échec, continuez. (Si des lettres peuvent apparaître plusieurs fois dans un mot, vous aurez peut-être besoin d'un compteur par lettre)
Lié (et honnêtement, je suis tenté de le considérer comme une dupe: stackoverflow.com/q/15045640/1079354 )
@JoeC J'ai parfois observé ça quand quelqu'un me posait des questions ici. Il ou elle a obtenu une réponse comme celle-ci Nous ne résolvons pas les travaux à domicile . Donc, je pense, écrire un code entier peut être hors de règles. J'ai donc encouragé une discussion.