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


시간 복잡도: 문자를 제거하기 위해 deleteCharAt()를 사용하므로 위 구현의 시간 복잡도는 실제로 O(mn + n^2)입니다. 선형 시간에 작동하도록 위의 솔루션을 최적화할 수 있습니다. deleteCharAr()을 사용하는 대신 빈 문자열을 만들고 여기에 필요한 문자만 추가할 수 있습니다.
StringBuilder는 입력 문자열에 대해 작업하는 데 사용됩니다. StringBuilder는 변경 가능하지만 String은 변경 불가능한 객체이기 때문입니다. 새 문자열을 생성하려면 O(n) 공간이 필요하므로 추가 공간은 O(n)입니다.
우리는 이 문제를 해결하기 위해 두 가지 접근 방식을 더 논의했습니다. 
문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 1  
문자열이 패턴으로 정의된 문자 순서를 따르는지 확인 | 세트 3