nikunjsoni

247

Jul 13th, 2021
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     int _n;
  3.     vector<pair<char, char>> candidates = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6','9'}, {'9','6'}};
  4.    
  5.     vector<string> helper(int n) {
  6.         vector<string> res;
  7.         if (n == 0) return {{}};
  8.         if (n == 1) return {"0", "1", "8"};
  9.    
  10.         auto temp = helper(n-2);
  11.         for (auto t : temp) {
  12.             for (auto p : candidates) {
  13.                 if (_n != n || p.first != '0') {
  14.                     string str = p.first + t + p.second;
  15.                     res.push_back(str);
  16.                 }
  17.             }
  18.         }
  19.        
  20.         return res;
  21.     }
  22.    
  23. public:
  24.     vector<string> findStrobogrammatic(int n) {
  25.         _n = n;
  26.         return helper(n);
  27.     }
  28. };
  29.  
  30. -------------------------------------
  31.  
  32. class Solution {
  33. public:
  34.     vector<string> findStrobogrammatic(int n) {
  35.         vector<string> ans;
  36.         if(n <= 0)  return ans;
  37.         string solution;
  38.         for(int i = 0; i < n; i++) solution += "0";
  39.         int l = 0, r = n-1;
  40.         dfs(l,r,solution,ans);
  41.         return ans;
  42.     }
  43.    
  44.     void dfs(int l, int r, string solution, vector<string>& ans){
  45.         if(l == r){
  46.             solution[l] = '0';
  47.             ans.push_back(solution);
  48.             solution[l] = '1';
  49.             ans.push_back(solution);
  50.             solution[l] = '8';
  51.             ans.push_back(solution);
  52.             return;
  53.         }
  54.         else if(l > r){
  55.             ans.push_back(solution);
  56.             return;
  57.         }
  58.        
  59.         solution[l] = solution[r] = '1';
  60.         dfs(l+1,r-1,solution,ans);
  61.         solution[l] = solution[r] = '8';
  62.         dfs(l+1,r-1,solution,ans);
  63.         solution[l] = '6', solution[r] = '9';
  64.         dfs(l+1,r-1,solution,ans);
  65.         solution[l] = '9', solution[r] = '6';
  66.         dfs(l+1,r-1,solution,ans);
  67.         if(l != 0){
  68.             solution[l] = solution[r] = '0';
  69.         dfs(l+1,r-1,solution,ans);
  70.         }  
  71.     }
  72. };
RAW Paste Data