Dada uma string de entrada e um padrão, verifique se os caracteres na string de entrada seguem a mesma ordem determinada pelos caracteres presentes no padrão. Suponha que não haja caracteres duplicados no padrão.
Outra solução para o mesmo problema é postada aqui .
Exemplos:
objeto para jsonobject java
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.
A ideia aqui é reduzir a string fornecida ao padrão fornecido. Para caracteres fornecidos no padrão, mantemos apenas os caracteres correspondentes na string. Na nova string, excluímos caracteres repetidos contínuos. A string modificada deve então ser igual ao padrão fornecido. Por último, comparamos a string modificada com o padrão fornecido e retornamos verdadeiro ou falso de acordo.
Ilustração:
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
Abaixo está a implementação das etapas acima.
// 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>
Saída:
Expected: true Actual: true Expected: false Actual: false Expected: false Actual: false Expected: true Actual: true
Complexidade de tempo: A complexidade de tempo das implementações acima é, na verdade, O(mn + n^2), pois usamos deleteCharAt() para remover caracteres. Podemos otimizar a solução acima para funcionar em tempo linear. Em vez de usar deleteCharAr() podemos criar uma string vazia e adicionar apenas os caracteres necessários a ela.
StringBuilder é usado para operar na string de entrada. Isso ocorre porque StringBuilder é mutável enquanto String é um objeto imutável. Para criar uma nova string é necessário espaço O(n), então o espaço extra é O(n).
Discutimos mais duas abordagens para resolver esse problema.
Verifique se a string segue a ordem dos caracteres definida por um padrão ou não | Conjunto 1
Verifique se a string segue a ordem dos caracteres definida por um padrão ou não | Conjunto 3
diferença de tigre e leão