Jayakrishna14

Check if DFS Strings Are Palindromes

Oct 19th, 2024
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<bool> findAnswer(vector<int>& parent, string s) {
  4.         const int n = parent.size();
  5.         vector<bool> ans(n, false);
  6.         unordered_map<int, vector<int>> mpp;
  7.        
  8.         for(int i=0; i<n; i++){
  9.             mpp[parent[i]].push_back(i);
  10.         }
  11.  
  12.         for(auto& el: mpp){
  13.             sort(el.second.begin(), el.second.end());
  14.         }
  15.  
  16.         auto isPalindrome = [](string& str){
  17.             int i = 0, j = str.size()-1;
  18.             while(i < j) if(str[i++]!=str[j--]) return false;
  19.             return true;
  20.         };
  21.  
  22.         string DFSstring;
  23.  
  24.         function<void(int)> dfs = [&](int x){
  25.             for(int child: mpp[x]) dfs(child);
  26.             DFSstring += s[x];
  27.         };
  28.  
  29.         for(int i=0; i<n; i++){
  30.             DFSstring = "";
  31.             dfs(i);
  32.             ans[i] = isPalindrome(DFSstring);
  33.         }
  34.  
  35.         return ans;
  36.     }
  37. };
Advertisement
Add Comment
Please, Sign In to add comment