Gegeven een invoerreeks en een patrooncontrole of tekens in de invoerreeks dezelfde volgorde volgen als bepaald door de tekens die in het patroon aanwezig zijn. Ga ervan uit dat er geen dubbele tekens in het patroon voorkomen.
Er wordt een andere oplossing voor hetzelfde probleem gepost hier .
Voorbeelden:
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.
Het idee hier is om de gegeven string terug te brengen tot het gegeven patroon. Voor tekens die in het patroon worden opgegeven, bewaren we alleen de overeenkomstige tekens in de string. In de nieuwe string verwijderen we continu herhaalde karakters. De gewijzigde string moet dan gelijk zijn aan het gegeven patroon. Ten slotte vergelijken we de gewijzigde tekenreeks met het gegeven patroon en retourneren dienovereenkomstig waar of onwaar.
Illustratie:
formaat Java-tekenreeks
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
Hieronder vindt u de implementatie van bovenstaande stappen.
// C++ code for the above approach #include
// 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 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# 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
<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>
Uitgang:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Tijdcomplexiteit: De tijdscomplexiteit van bovenstaande implementaties is eigenlijk O(mn + n^2) omdat we deleteCharAt() gebruiken om tekens te verwijderen. We kunnen bovenstaande oplossing optimaliseren om in lineaire tijd te werken. In plaats van deleteCharAr() te gebruiken, kunnen we een lege string maken en er alleen de vereiste tekens aan toevoegen.
StringBuilder wordt gebruikt om te werken met een invoerreeks. Dit komt omdat StringBuilder veranderlijk is, terwijl String een onveranderbaar object is. Om een nieuwe string te maken is O(n) ruimte nodig, dus extra ruimte is O(n).
We hebben nog twee benaderingen besproken om dit probleem op te lossen.
Controleer of de tekenreeks de volgorde volgt van tekens die door een patroon zijn gedefinieerd of niet | Set 1
Controleer of de tekenreeks de volgorde volgt van tekens die door een patroon zijn gedefinieerd of niet | Set 3