Adott egy bemeneti karakterlánc és egy minta ellenőrizze, hogy a bemeneti karakterlánc karakterei ugyanazt a sorrendet követik-e, mint amit a mintában jelen lévő karakterek határoznak meg. Tegyük fel, hogy nem lesznek ismétlődő karakterek a mintában.
Ugyanennek a problémának egy másik megoldása is megjelent itt .
Példák:
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.
Itt az az ötlet, hogy az adott karakterláncot a megadott mintára redukáljuk. A mintában megadott karaktereknél csak a megfelelő karaktereket tartjuk meg a karakterláncban. Az új karakterláncban töröljük a folyamatosan ismétlődő karaktereket. A módosított karakterláncnak ekkor egyenlőnek kell lennie a megadott mintával. Végül összehasonlítjuk a módosított karakterláncot a megadott mintával, és ennek megfelelően adjuk vissza a true értéket a false értékkel.
Ábra:
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
Az alábbiakban bemutatjuk a fenti lépések végrehajtását.
// 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>
Kimenet:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Időbeli összetettség: A fenti megvalósítások időbeli összetettsége valójában O(mn + n^2), mivel a deleteCharAt()-t használjuk a karakterek eltávolítására. A fenti megoldást úgy tudjuk optimalizálni, hogy lineáris időben működjön. A deleteCharAr() használata helyett létrehozhatunk egy üres karakterláncot, és csak a szükséges karaktereket adhatjuk hozzá.
A StringBuilder a bemeneti karakterláncok kezelésére szolgál. Ennek az az oka, hogy a StringBuilder változtatható, míg a String megváltoztathatatlan objektum. Egy új karakterlánc létrehozása O(n) szóközt vesz igénybe, tehát az extra szóköz O(n).
A probléma megoldására további két megközelítést tárgyaltunk.
Ellenőrizze, hogy a karakterlánc követi-e a minta által meghatározott karakterek sorrendjét, vagy sem | 1. készlet
Ellenőrizze, hogy a karakterlánc követi-e a minta által meghatározott karakterek sorrendjét, vagy sem | 3. készlet