Infosys HackWithInfy OA | DSE/Sp Role | Kumar K | 15 LPA | SET 17

Question

Answer 1

#include<bits/stdc++.h>

using namespace std;

char rot13(char c){

    if(c>='a' && c<='z'){

        return (c-'a'+13)%26 +'a';

    }

    return c;

}

int solve(string W1,string W2){

    int n = W1.size();

    int m = W2.size();

    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(m+1,vector<int>(2,-1)));

    auto getmin = [&](auto& self,int i,int j,int rot) ->int {

          if(i==n && j==m) return 0;

          if(i==n) return m-j;

          if(j==m) return n-i;

          if(dp[i][j][rot]!=-1) return   dp[i][j][rot];

          char c1 = (rot==1)? rot13(W1[i]):W1[i];

          char c2 = W2[j];

          int ans = 1e9 ;

          if(c1==c2) ans = min(ans,self(self,i+1,j+1,rot));

          ans = min(ans,1+ self(self,i+1,j+1,rot)); //replace

          ans = min(ans,1+self(self,i+1,j,1-rot)); // delete

          ans = min(ans,self(self,i,j+1,1-rot)); //insert

          return dp[i][j][rot] = ans;

    }

    return getmin(getmin,0,0,0);

 

 

}