SHARE
TWEET

567. Permutation in String

Marvin48 Aug 13th, 2017 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // https://leetcode.com/problems/permutation-in-string
  2.  
  3. #include <iostream>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. class Solution {
  9. public:
  10.     bool checkInclusion(string s1, string s2) {
  11.         map<char, int> charData;
  12.         for (char c : s1){
  13.             charData[c]++;
  14.         }
  15.  
  16.         map<char, int> *tmp = nullptr;
  17.         int target = s1.size(), cur = 0;
  18.         for (int i = 0; i < s2.size(); i++){
  19.             char c = s2[i];
  20.  
  21.             if (charData[c] != 0){
  22.                 if (tmp == nullptr)
  23.                     tmp = new map<char, int>(charData);
  24.                 if (tmp->at(c) > 0){
  25.                     tmp->at(c)--;
  26.  
  27.                     if (++cur == target){
  28.                         return true;
  29.                     }
  30.                 }
  31.                 else{
  32.                     //go back;
  33.                     int rewindCount = charData[c];
  34.  
  35.                     while (rewindCount > 0){
  36.                         if (s2[--i] == c){
  37.                             rewindCount--;
  38.                         }
  39.                     }
  40.  
  41.                     delete tmp;
  42.                     tmp = new map<char, int>(charData);
  43.                     cur = 0;
  44.                 }
  45.  
  46.             }
  47.             else{
  48.                 if (tmp != nullptr){
  49.                     delete tmp;
  50.                     tmp = nullptr;
  51.                 }
  52.                 cur = 0;
  53.             }
  54.         }
  55.  
  56.         if (tmp != nullptr){
  57.             delete tmp;
  58.             tmp = nullptr;
  59.         }
  60.  
  61.         return false;
  62.     }
  63. };
RAW Paste Data
Top