Java: Comment vérifier si les caractères sont contenus dans une chaîne

Question

soir,

J'essaie de trouver la meilleure solution pour résoudre ce problème:

Entrée:

String1 = "algrtvy"; 
String2 = "alg"; 
String3 = "gvy"; 
String4 = "mgr"; 
String5 = "aall"; 

Les caractères de str2, 3, 4, 5 sont-ils contenus dans 1?

Sortie

true 
true 
false 
false 

donc, je ne suis pas la vérification de la séquence (sous-chaîne), mais pour les personnages simples.

Des conseils? Je suis à la recherche de la solution à jeun en temps de calcul.

Solution:

Cette solution est une version mise en œuvre de la réponse du @ davidxxx.

public boolean haveChars(String longerString, String shorterString) { 
    String chars = longerString; 
    for (char c : shorterString.toCharArray()){ 
     int index = chars.indexOf(c); 
     if (index == -1) { 
      return false; 
     } else { 
      chars = chars.substring(0,index) + chars.substring(index + 1); 
     }  
    } 
    return true; 
} 

Answer 1

1) Stocker dans une valeur int le nombre de caractères à trouver dans l'entrée. C'est le compteur qui permettra de savoir si la correspondance est réussie.

Et également faire une copie du modèle actuel pour correspondre.
Ce n'est pas obligatoire car String sont immuables mais cela rend les choses plus claires.

2) Itérez sur chaque caractère contenu dans l'entrée que vous essayez de faire correspondre avec la copie de votre modèle.

3) Dès qu'un caractère correspond, décrémentez le compteur et retirez-le de la copie du modèle.

4) Dès que le compteur est évalué à 0, cela signifie que l'entrée et le modèle correspondent.

5) Si après la boucle des caractères de l'entrée, le compteur n'est pas évalué à 0, cela signifie que l'entrée et le modèle ne correspondent pas.

Vous pourriez avoir une méthode comme ça:

public static boolean isMatch(String model, String input) { 

    int nbCharacterRemaningToFind = input.length(); 
    String copyModel = model; 

    for (char c : input.toCharArray()) { 
     String cInString = String.valueOf(c); 

     if (copyModel.contains(cInString)) { 
      copyModel = copyModel.replaceFirst(cInString, ""); 
      nbCharacterRemaningToFind--; 
      if (nbCharacterRemaningToFind == 0) { 
       return true; 
      } 
     } 

    } 

    return false; 
} 

Answer 2

Si votre chaîne est courte, vous pouvez simplement utiliser

String string = "abcdefgh"; 
String sub = "adf"; 

boolean ok = sub.chars().allMatch(c -> string.indexOf((char) c) >= 0); 

Si M est la taille de la chaîne, et N est la taille des sous, il est O (N * M) dans le pire Cas.

Si elle est grande, ou si vous voulez faire appliquer le contrôle sur la même chaîne plusieurs fois, vous pouvez commencer par faire un ensemble, et utiliser le même principe:

Set<Character> set = string.chars().mapToObj(c -> ((char) c)).collect(Collectors.toSet()); 
ok = sub.chars().allMatch(c -> set.contains((char) c)); 

Ceci est O (M) + O (N).

Une autre possibilité consiste à faire la place d'un ensemble de la sous-chaîne:

Set<Character> subset = sub.chars().mapToObj(c -> ((char) c)).collect(Collectors.toSet()); 
for (int i = 0; i < string.length() && !subset.isEmpty(); i++) { 
    subset.remove(string.charAt(i)); 
} 
ok = subset.isEmpty(); 

Encore une fois O (M) + O (N).

Vous devriez maintenant mesurer vos entrées attendues. Mais attention: les benchmarks en Java sont difficiles.

Answer 3

Vous pouvez simplement vérifier créer une nouvelle fonction (containsEachChar) qui vérifie la contient comme ceci: `

public boolean containsEachChar(String string1, String string2) { 
     for (char c : string2.toCharArray()) { 
      if(string1.indexOf(c) == -1){ 
       return false; 
      } 
     } 
     return true; 
} 
`  

La déclaration string1.indexOf (c) renvoie la position du 'c' dans 'string1'. Dans le cas où 'c' n'est pas présent dans 'string1', -1 est retourné.

Maintenant, vous pouvez appeler méthode ci-dessus à partir de votre principale méthode: `

 public static void main(String[] args) { 
     String string1 = "algrtvy"; 
     String string2 = "alg"; 
     String string3 = "gvy"; 
     String string4 = "mgr"; 
     System.out.println(containsEachChar(string1, string2)); 
     System.out.println(containsEachChar(string1, string3)); 
     System.out.println(containsEachChar(string1, string4)); 
    } 

Sortie: vrai vrai faux

Qu'est-ce que le code containsEachChar fait est que,

1. Il itère les caractères dans string2.
2. Comme il n'est pas indispensable de vérifier d'autres caractères dans string2 si la valeur string1.indexOf (c) est -1, la fonction renvoie simplement false.

Answer 4

RemarqueCet est probablement une solution inefficace, mais ce que je suis en train de faire ici est d'utiliser containsAll qui vérifie si le contenu d'une collection est contenu dans une autre collection

chaîne chaîne1 = " algrtvy ";

//turn it to arraylist 
    List<String> string1ArrayList = Arrays.asList(string1.split("")); 
    String string2 = "alg"; 
    String string3 = "gvy"; 
    String string4 = "mgr"; 
    String string5 = "aall"; 

    //check its in the arraylist 
    System.out.println(string1ArrayList.containsAll(Arrays.asList(string2.split("")))); 
    System.out.println(string1ArrayList.containsAll(Arrays.asList(string3.split("")))); 
    System.out.println(string1ArrayList.containsAll(Arrays.asList(string4.split("")))); 
    System.out.println(string1ArrayList.containsAll(Arrays.asList(string5.split("")))); 

*

results: true true false true

*