J'essaie de créer une fonction qui imprime le nombre de caractères communs dans n chaînes données. (notez que les caractères peuvent être utilisés plusieurs fois)
J'ai du mal à effectuer cette opération sur n chaînes Cependant je l'ai fait pour 2 chaînes sans aucun caractère répété plus d'une fois.
J'ai posté mon code .
3 abacd aaxyz aatre
3 abcaa bcbd bgc 3
il y a peut-être des chances qu'un même personnage soit présent plusieurs fois dans une chaîne et vous n'êtes pas censé éliminer ces caractères à la place vérifiez le non. souvent, ils sont répétés dans d'autres chaînes. par exemple
public class CommonChars {
public static void main(String[] args) {
String str1 = "abcd";
String str2 = "bcde";
StringBuffer sb = new StringBuffer();
// get unique chars from both the strings
str1 = uniqueChar(str1);
str2 = uniqueChar(str2);
int count = 0;
int str1Len = str1.length();
int str2Len = str2.length();
for (int i = 0; i < str1Len; i++) {
for (int j = 0; j < str2Len; j++) {
// found match stop the loop
if (str1.charAt(i) == str2.charAt(j)) {
count++;
sb.append(str1.charAt(i));
break;
}
}
}
System.out.println("Common Chars Count : " + count + "\nCommon Chars :" +
sb.toString());
}
public static String uniqueChar(String inputString) {
String outputstr="",temp="";
for(int i=0;i<inputstr.length();i++) {
if(temp.indexOf(inputstr.charAt(i))<0) {
temp+=inputstr.charAt(i);
}
}
System.out.println("completed");
return temp;
}
}
la sortie devrait être 2
ce sera mieux si j'obtiens une solution en java
5 Réponses :
Une meilleure stratégie pour votre problème consiste à utiliser cette méthode:
int[][] result = new int[n][26]
for(int i = 0; i<strings.length;i++){
result[i] = countChars(s);
}
// now if you sum the min common chars for each counter you are ready
int commonChars = 0;
for(int i = 0; i< 26;i++){
int min = result[0][i];
for(int i = 1; i< n;i++){
if(min>result[j][i]){
min = result[j][i];
}
}
commonChars+=min;
}
Maintenant, si vous avez n chaînes (chaîne [] chaînes), trouvez simplement le minimum de caractères communs pour chaque lettre:
public int[] countChars(String s){
int[] count = new int[26];
for(char c: s.toCharArray()){
count[c-'a']++;
}
return count;
}
Obtenez la liste des caractères pour chaque chaîne:
chars1.retainAll(chars2); // retain in chars1 only the chars that are contained in the chars2 also System.out.println(chars1.size());
Ensuite, utilisez la méthode retentionAll :
List<Character> chars1 = s1.chars() // list of chars for first string
.mapToObj(c -> (char) c)
.collect(Collectors.toList());
List<Character> chars2 = s2.chars() // list of chars for second string
.mapToObj(c -> (char) c)
.collect(Collectors.toList());
Si vous voulez obtenir un nombre de caractères uniques, utilisez simplement Collectors.toSet () au lieu de toList()
Eh bien si on opte pour le hachage:
public static String uniqueChars(String first, String second) {
boolean[] hash = new boolean[26];
StringBuilder sb = new StringBuilder();
for (char c : first.toLowerCase().toCharArray()) {
hash[c - 'a'] = true;
}
for(char c : second.toLowerCase().toCharArray()){
if(hash[c - 'a']){
sb.append(c);
hash[c - 'a'] = false;
}
}
return sb.toString();
}
Ceci utilise bucketsort qui donne une complexité n + m mais nécessite les 26 buckets (le tableau "hash"). Je ne peux pas faire mieux en ce qui concerne la complexité car vous devez regarder chaque lettre au moins une fois, ce qui résume jusqu'à n + m.
Insitu, le mieux que vous puissiez obtenir est à mon humble avis quelque part dans la gamme de O (n log (n)).
Votre approche se situe quelque part dans la ligue de O (n²)
Addon: si vous avez besoin des caractères sous forme de chaîne (essentiellement la même comme ci-dessus avec count est la longueur de la chaîne retournée):
public static int uniqueChars(String first, String second) {
boolean[] hash = new boolean[26];
int count = 0;
//reduce first string to unique letters
for (char c : first.toLowerCase().toCharArray()) {
hash[c - 'a'] = true;
}
//reduce to unique letters in both strings
for(char c : second.toLowerCase().toCharArray()){
if(hash[c - 'a']){
count++;
hash[c - 'a'] = false;
}
}
return count;
}
System.out.println(getCommonCharacters("abcd", "bcde")); // bcd
Vous devez convertir toutes les String s en Set de Character s et conserver toutes celles du premier. La solution ci-dessous contient de nombreux emplacements qui pourraient être optimisés, mais vous devez comprendre l'idée générale.
[n, o]
Le code ci-dessus est imprimé:
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] args) {
List<String> input = Arrays.asList("jonas", "ton", "bonny");
System.out.println(findCommonCharsFor(input));
}
public static Collection<Character> findCommonCharsFor(List<String> strings) {
if (strings == null || strings.isEmpty()) {
return Collections.emptyList();
}
Set<Character> commonChars = convertStringToSetOfChars(strings.get(0));
strings.stream().skip(1).forEach(s -> commonChars.retainAll(convertStringToSetOfChars(s)));
return commonChars;
}
private static Set<Character> convertStringToSetOfChars(String string) {
if (string == null || string.isEmpty()) {
return Collections.emptySet();
}
Set<Character> set = new HashSet<>(string.length() + 10);
for (char c : string.toCharArray()) {
set.add(c);
}
return set;
}
}
J'ai déjà essayé la première approche mais pouvez-vous suggérer comment procéder avec votre deuxième cas