Advertisement
HjHimansh

Swap Adjacent in LR String

Aug 31st, 2020
1,832
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     //returns whether start[index....start.size()-1] can be converted to end[index...end.size()-1]
  5.     bool h_canTransform(string start, string end, int index, deque<int> &posX, deque<int> &posL, deque<int> &posR){
  6.         if(index == start.size()){
  7.             return true;
  8.         }
  9.          
  10.         if(!posX.empty() && posX.front() == index){
  11.             posX.pop_front();
  12.         }
  13.         if(!posL.empty() && posL.front() == index){
  14.             posL.pop_front();
  15.         }
  16.         if(!posR.empty() && posR.front() == index){
  17.             posR.pop_front();
  18.         }
  19.        
  20.         if(start[index] == end[index]){
  21.             return h_canTransform(start, end, index+1, posX, posL, posR);
  22.         }
  23.        
  24.         if(start[index] == 'X' && end[index] == 'L'){
  25.             if(posL.empty())    return false;
  26.             int pL = posL.front();
  27.  
  28.            
  29.             if(posR.empty() || posR.front() > pL){
  30.                 swap(start[index], start[pL]);
  31.                 posL.pop_front();
  32.                 return h_canTransform(start, end, index+1, posX, posL, posR);        
  33.             }
  34.            
  35.             return false;
  36.         }
  37.         if(start[index] == 'R' && end[index]=='X'){
  38.             //brint X to start[index]
  39.             if(posX.empty())    return false;
  40.             int pX = posX.front();
  41.             if(posL.empty() || posL.front() > pX){
  42.                 swap(start[index], start[pX]);
  43.                 posX.pop_front();
  44.                 return h_canTransform(start, end, index+1, posX, posL, posR);
  45.             }
  46.             return false;
  47.         }
  48.         return false;
  49.     }
  50.    
  51.     bool canTransform(string start, string end) {
  52.         if(start.size() != end.size()){
  53.             return false;
  54.         }
  55.         deque<int> posL;
  56.         deque<int> posR;
  57.         deque<int> posX;
  58.         for(int i=0; i<start.size(); i++){
  59.             if(start[i]=='L'){
  60.                 posL.push_back(i);
  61.             }
  62.             if(start[i]=='R'){
  63.                 posR.push_back(i);
  64.             }
  65.             if(start[i]=='X'){
  66.                 posX.push_back(i);
  67.             }
  68.         }
  69.        
  70.         return h_canTransform(start, end, 0, posX, posL, posR);
  71.     }
  72. };
  73.  
  74.  
Advertisement
RAW Paste Data Copied
Advertisement