logo

TechCodeview

Проверете дали низът следва реда на символите, дефиниран от модел, или не | Комплект 2

Като се има предвид входен низ и шаблон, проверете дали знаците във входния низ следват същия ред, както е определено от символите, присъстващи в шаблона. Да предположим, че няма да има дублирани знаци в шаблона.
Публикувано е друго решение на същия проблем тук .
Примери:  
 

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.


 




Идеята тук е да се намали дадения низ до дадения модел. За знаците, дадени в шаблона, запазваме само съответните знаци в низа. В новия низ изтриваме непрекъснато повтарящи се знаци. Тогава модифицираният низ трябва да е равен на дадения модел. Накрая сравняваме модифицирания низ с дадения модел и съответно връщаме true или false.
Илюстрация: 
 

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


По-долу е изпълнението на горните стъпки.
 

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>

Изход:  
 



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


Времева сложност: Времевата сложност на горните реализации всъщност е O(mn + n^2), тъй като използваме deleteCharAt() за премахване на знаци. Можем да оптимизираме горното решение за работа в линейно време. Вместо да използваме deleteCharAr(), можем да създадем празен низ и да добавим само необходимите символи към него.
StringBuilder се използва за работа с въведен низ. Това е така, защото StringBuilder е променлив, докато String е неизменен обект. Създаването на нов низ изисква O(n) място, така че допълнителното пространство е O(n).
Обсъдихме още два подхода за решаване на този проблем. 
Проверете дали низът следва реда на символите, дефиниран от модел, или не | Комплект 1  
Проверете дали низът следва реда на символите, дефиниран от модел, или не | Комплект 3