logo

TechCodeview

Vérifier si la chaîne suit ou non l'ordre des caractères défini par un modèle | Ensemble 2

Étant donné une chaîne d'entrée et un modèle, vérifiez si les caractères de la chaîne d'entrée suivent le même ordre que celui déterminé par les caractères présents dans le modèle. Supposons qu’il n’y ait pas de caractères en double dans le modèle.
Une autre solution au même problème est publiée ici .
Exemples :  
 

Input: string = 'engineers rock' pattern = 'er'; Output: true All 'e' in the input string are before all 'r'. Input: string = 'engineers rock' pattern = 'egr'; Output: false There are two 'e' after 'g' in the input string. Input: string = 'engineers rock' pattern = 'gsr'; Output: false There are one 'r' before 's' in the input string.


 




L'idée ici est de réduire la chaîne donnée au modèle donné. Pour les caractères donnés dans le modèle, nous ne conservons que les caractères correspondants dans la chaîne. Dans la nouvelle chaîne, nous supprimons les caractères répétés en continu. La chaîne modifiée doit alors être égale au modèle donné. Enfin, nous comparons la chaîne modifiée au modèle donné et renvoyons vrai ou faux en conséquence.
Illustration: 
 

str = 'bfbaeadeacc' pat[] = 'bac' 1) Remove extra characters from str (characters that are not present in pat[] str = 'bbaaacc' [f e and d are removed] 3) Removed consecutive repeating occurrences of characters str = 'bac' 4) Since str is same as pat[] we return true


Vous trouverez ci-dessous la mise en œuvre des étapes ci-dessus.
 

C++ 
// C++ code for the above approach #include    #include  using namespace std; bool followsPattern(string str string pattern) {  // Insert all characters of pattern in a hash set  unordered_set<char> patternSet;  for (int i = 0; i < pattern.length(); i++) {  patternSet.insert(pattern[i]);  }  // Build modified string (string with characters only from pattern are taken)  string modifiedStr = str;  for (int i = str.length() - 1; i >= 0; i--) {  if (patternSet.find(str[i]) == patternSet.end()) {  modifiedStr.erase(i 1);  }  }  // Remove more than one consecutive occurrences of pattern characters from modified string  for (int i = modifiedStr.length() - 1; i > 0; i--) {  if (modifiedStr[i] == modifiedStr[i - 1]) {  modifiedStr.erase(i 1);  }  }  // After above modifications the length of modified string must be same as pattern length  if (pattern.length() != modifiedStr.length()) {  return false;  }  // And pattern characters must also be same as modified string characters  for (int i = 0; i < pattern.length(); i++) {  if (pattern[i] != modifiedStr[i]) {  return false;  }  }  return true; } int main() {  string str = 'engineers rock';  string pattern = 'er';  cout << 'Expected: true Actual: ' << followsPattern(str pattern) << endl;  str = 'engineers rock';  pattern = 'egr';  cout << 'Expected: false Actual: ' << followsPattern(str pattern) << endl;  str = 'engineers rock';  pattern = 'gsr';  cout << 'Expected: false Actual: ' << followsPattern(str pattern) << endl;  str = 'engineers rock';  pattern = 'eger';  cout << 'Expected: true Actual: ' << followsPattern(str pattern) << endl;  return 0; } // This code is contributed by adityashatmfh
Java 
// Java program to check if characters of a string follow // pattern defined by given pattern. import java.util.*; public class OrderOfCharactersForPattern {  public static boolean followsPattern(String str String pattern)  {  // Insert all characters of pattern in a hash set  Set<Character> patternSet = neHashSet<>();  for (int i=0; i<pattern.length(); i++)  patternSet.add(pattern.charAt(i));  // Build modified string (string with characters only from  // pattern are taken)  StringBuilder modifiedString = new StringBuilder(str);  for (int i=str.length()-1; i>=0; i--)  if (!patternSet.contains(modifiedString.charAt(i)))  modifiedString.deleteCharAt(i);  // Remove more than one consecutive occurrences of pattern  // characters from modified string.  for (int i=modifiedString.length()-1; i>0; i--)  if (modifiedString.charAt(i) == modifiedString.charAt(i-1))  modifiedString.deleteCharAt(i);  // After above modifications the length of modified string  // must be same as pattern length  if (pattern.length() != modifiedString.length())  return false;  // And pattern characters must also be same as modified string  // characters  for (int i=0; i<pattern.length(); i++)  if (pattern.charAt(i) != modifiedString.charAt(i))  return false;  return true;  }  // Driver program  int main()  {  String str = 'engineers rock';  String pattern = 'er';  System.out.println('Expected: true Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'egr';  System.out.println('Expected: false Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'gsr';  System.out.println('Expected: false Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'eger';  System.out.println('Expected: true Actual: ' +  followsPattern(str pattern));  return 0;  } }
Python3 
# Python3 program to check if characters of  # a string follow pattern defined by given pattern. def followsPattern(string pattern): # Insert all characters of pattern in a hash set patternSet = set() for i in range(len(pattern)): patternSet.add(pattern[i]) # Build modified string (string with characters  # only from pattern are taken) modifiedString = string for i in range(len(string) - 1 -1 -1): if not modifiedString[i] in patternSet: modifiedString = modifiedString[:i] +  modifiedString[i + 1:] # Remove more than one consecutive occurrences  # of pattern characters from modified string. for i in range(len(modifiedString) - 1 0 -1): if modifiedString[i] == modifiedString[i - 1]: modifiedString = modifiedString[:i] +  modifiedString[i + 1:] # After above modifications the length of  # modified string must be same as pattern length if len(pattern) != len(modifiedString): return False # And pattern characters must also be same  # as modified string characters for i in range(len(pattern)): if pattern[i] != modifiedString[i]: return False return True # Driver Code if __name__ == '__main__': string = 'engineers rock' pattern = 'er' print('Expected: true Actual:' followsPattern(string pattern)) string = 'engineers rock' pattern = 'egr' print('Expected: false Actual:' followsPattern(string pattern)) string = 'engineers rock' pattern = 'gsr' print('Expected: false Actual:' followsPattern(string pattern)) string = 'engineers rock' pattern = 'eger' print('Expected: true Actual:' followsPattern(string pattern)) # This code is contributed by # sanjeev2552
C# 
// C# program to check if characters of a string follow // pattern defined by given pattern. using System; using System.Collections.Generic; using System.Text; class GFG {  public static bool followsPattern(String str String pattern)  {  // Insert all characters of pattern in a hash set  HashSet<char> patternSet = new HashSet<char>();  for (int i = 0; i < pattern.Length; i++)  patternSet.Add(pattern[i]);  // Build modified string (string with characters   // only from pattern are taken)  StringBuilder modifiedString = new StringBuilder(str);  for (int i = str.Length - 1; i >= 0; i--)  if (!patternSet.Contains(modifiedString[i]))  modifiedString.Remove(i 1);  // Remove more than one consecutive occurrences of pattern  // characters from modified string.  for (int i = modifiedString.Length - 1; i > 0; i--)  if (modifiedString[i] == modifiedString[i - 1])  modifiedString.Remove(i 1);  // After above modifications the length of modified string  // must be same as pattern length  if (pattern.Length != modifiedString.Length)  return false;  // And pattern characters must also be same   // as modified string characters  for (int i = 0; i < pattern.Length; i++)  if (pattern[i] != modifiedString[i])  return false;  return true;  }  // Driver program  public static void Main(String[] args)  {  String str = 'engineers rock';  String pattern = 'er';  Console.WriteLine('Expected: true Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'egr';  Console.WriteLine('Expected: false Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'gsr';  Console.WriteLine('Expected: false Actual: ' +  followsPattern(str pattern));  str = 'engineers rock';  pattern = 'eger';  Console.WriteLine('Expected: true Actual: ' +  followsPattern(str pattern));  } } // This code is contributed by 29AjayKumar
JavaScript 
<script> // Javascript program to check if characters of a string follow // pattern defined by given pattern. function followsPattern(str pattern) {  // Insert all characters of pattern in a hash set  let patternSet = new Set();  for (let i=0; i<pattern.length; i++)  patternSet.add(pattern[i]);    // Build modified string (string with characters only from  // pattern are taken)  let modifiedString = (str).split('');  for (let i=str.length-1; i>=0; i--)  if (!patternSet.has(modifiedString[i]))  modifiedString.splice(i1);    // Remove more than one consecutive occurrences of pattern  // characters from modified string.  for (let i=modifiedString.length-1; i>0; i--)  if (modifiedString[i] == modifiedString[i-1])  modifiedString.splice(i1);    // After above modifications the length of modified string  // must be same as pattern length  if (pattern.length != modifiedString.length)  return false;    // And pattern characters must also be same as modified string  // characters  for (let i=0; i<pattern.length; i++)  if (pattern[i] != modifiedString[i])  return false;    return true; } // Driver program let str = 'engineers rock'; let pattern = 'er'; document.write('Expected: true Actual: ' +  followsPattern(str pattern)+'  
'); str = 'engineers rock'; pattern = 'egr'; document.write('Expected: false Actual: ' +  followsPattern(str pattern)+'  
'); str = 'engineers rock'; pattern = 'gsr'; document.write('Expected: false Actual: ' +  followsPattern(str pattern)+'  
'); str = 'engineers rock'; pattern = 'eger'; document.write('Expected: true Actual: ' +  followsPattern(str pattern)+'  
'); // This code is contributed by rag2127 </script>

Sortir:  
 



Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true


Complexité temporelle : La complexité temporelle des implémentations ci-dessus est en fait O(mn + n^2) car nous utilisons deleteCharAt() pour supprimer des caractères. Nous pouvons optimiser la solution ci-dessus pour travailler en temps linéaire. Au lieu d'utiliser deleteCharAr(), nous pouvons créer une chaîne vide et y ajouter uniquement les caractères requis.
StringBuilder est utilisé pour opérer sur la chaîne d'entrée. En effet, StringBuilder est mutable alors que String est un objet immuable. Pour créer une nouvelle chaîne, il faut un espace O(n), donc l'espace supplémentaire est O(n).
Nous avons discuté de deux autres approches pour résoudre ce problème. 
Vérifier si la chaîne suit ou non l'ordre des caractères défini par un modèle | Ensemble 1  
Vérifier si la chaîne suit ou non l'ordre des caractères défini par un modèle | Ensemble 3