4 problems solved.

lintcoder · lintcoder · commit adf05b7993f5 · 2020-01-11T20:46:31.000+08:00
diff --git a/src/1309.cpp b/src/1309.cpp
@@ -0,0 +1,24 @@
+string freqAlphabets(string s) {
+        int len = s.size();
+        int i = 0;
+        string res;
+        while (i < len)
+        {
+            int p = s.find('#', i);
+            if (p != -1)
+            {
+                for (; i < p-2; ++i)
+                    res.push_back(s[i]-'1'+'a');
+                int t = (s[i]-'0')*10+(s[i+1]-'0');
+                res.push_back(t-10+'j');
+                i = p+1;
+            }
+            else
+            {
+                for (; i < len; ++i)
+                    res.push_back(s[i]-'1'+'a');
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/3.cpp b/src/3.cpp
@@ -0,0 +1,38 @@
+int lengthOfLongestSubstring(string s) {
+        int len = s.size();
+        if (len <= 1)
+            return len;
+        
+        map<char, int> pos;
+        pos[s[0]] = 0;
+        
+        int i = 1, tmp = 1;
+        int maxlen = 1;
+        int index = 0;
+        while (i < len)
+        {
+            if (pos.find(s[i]) == pos.end() || pos[s[i]] == -1)
+            {
+                ++tmp;
+                pos[s[i]] = i;
+                ++i;
+            }
+            else
+            { 
+                if (tmp > maxlen)
+                    maxlen = tmp;
+                int t = pos[s[i]];
+                for (int j = index; j <=t; ++j)
+                    pos[s[j]] = -1;
+                tmp = i-t;
+                pos[s[i]] = i;
+                index = t+1;
+                ++i;
+            }
+        }
+        
+        if (tmp > maxlen)
+            maxlen = tmp;
+        
+        return maxlen;
+    }
diff --git a/src/78.cpp b/src/78.cpp
@@ -0,0 +1,23 @@
+vector<vector<int>> subsets(vector<int>& nums) {
+        vector<vector<int>> res;
+        res.push_back({});
+        int len = nums.size();
+        if (len == 0)
+            return res;
+        
+        vector<int> vec;
+        search(nums, 0, len, vec, res);
+        
+        return move(res);
+    }
+    
+    void search(vector<int>& nums, int index, int len, vector<int>& vec, vector<vector<int>>& res)
+    {
+        for (int i = index; i < len; ++i)
+        {
+            vector<int> tmp(vec);
+            tmp.push_back(nums[i]);
+            res.push_back(tmp);
+            search(nums, i+1, len, tmp, res);
+        }
+    }
diff --git a/src/79.cpp b/src/79.cpp
@@ -0,0 +1,63 @@
+bool exist(vector<vector<char>>& board, string word) {
+        int row = board.size();
+        if (row == 0)
+            return word == "";
+        int col = board[0].size();
+        
+        if (col == 0)
+            return word == "";
+        int total = row*col;
+        
+        int sz = word.size();
+        for (int i = 0; i < row; ++i)
+        {
+            for (int j = 0; j < col; ++j)
+            {
+                if (board[i][j] == word[0])
+                {
+                    vector<int> flag(total, 0);
+                    flag[i*col+j] = 1;
+                    bool res = search(board, row, col, i, j, 1, sz, word, flag);
+                    if (res)
+                    {
+                        return true;
+                    }
+                }
+            }
+        }
+        
+        return false;
+    }
+    
+    bool search(const vector<vector<char>>& board, int row, int col, int r, int c, int ct, int sz, const string& word, vector<int>& flag)
+    {
+        if (ct == sz)
+            return true;
+        bool res = false;
+        if (r > 0 && flag[(r-1)*col+c] == 0 && board[r-1][c] == word[ct])
+        {
+            vector<int> flag1(flag);
+            flag1[(r-1)*col+c] = 1;
+            res = search(board, row, col, r-1, c, ct+1, sz, word, flag1);
+        }    
+        if (!res && r < row-1 && flag[(r+1)*col+c] == 0 && board[r+1][c] == word[ct])
+        {
+            vector<int> flag1(flag);
+            flag1[(r+1)*col+c] = 1;
+            res = search(board, row, col, r+1, c, ct+1, sz, word, flag1);
+        }
+        if (!res && c > 0 && flag[r*col+c-1] == 0 && board[r][c-1] == word[ct])
+        {
+            vector<int> flag1(flag);
+            flag1[r*col+c-1] = 1;
+            res = search(board, row, col, r, c-1, ct+1, sz, word, flag1);
+        }
+        if (!res && c < col-1 && flag[r*col+c+1] == 0 && board[r][c+1] == word[ct])
+        {
+            vector<int> flag1(flag);
+            flag1[r*col+c+1] = 1;
+            res = search(board, row, col, r, c+1, ct+1, sz, word, flag1);
+        }
+        
+        return res;
+    }
