Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

104. Maximum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth{ 0 };
        int tmp{ 0 };
        backTrack(root, depth, tmp);
        return depth;
    }
private:
    void backTrack(TreeNode* root, int& depth, int& tmp)
    {
        if(!root) return;
        ++tmp;
        depth = max(depth, tmp);
        backTrack(root->left, depth, tmp);
        backTrack(root->right, depth, tmp);
        --tmp;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left) + 1, maxDepth(root->right) + 1);
    }
};

待优化空间占用

Posted on Edited on In Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

155. Min Stack

抄的dicussion中的一种实现方法，真的帅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        topEle = nullptr;
    }    
    void push(int val) {
        if(!topEle)
            topEle = new Node(val, val);
        else
            topEle = new Node(val, min(topEle->min, val), topEle);
    }
    
    void pop() {
        auto tmp = topEle;
        topEle = tmp->next;
        delete tmp;
    }
    
    int top() {
        return topEle->val;
    }
    
    int getMin() {
        return topEle->min;
    }
private:
    struct Node {
        int val;
        int min;
        Node* next;
        Node () : val(0), min(INT_MAX), next(nullptr) {}
        Node (int val, int min) : val(val), min(min), next(nullptr) {}
        Node (int val, int min, Node* next) : val(val), min(min), next(next) {}
    };
    Node* topEle;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

使用两个栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        values.push(x);
        if(minValues.empty() || x <= minValues.top())
            minValues.push(x);
    }
    
    void pop() {
        if(minValues.top() == values.top())
            minValues.pop();
        values.pop();
    }
    
    int top() {
        return values.top();
    }
    
    int getMin() {
        return minValues.top();
    }
private:
    stack<int> values;
    stack<int> minValues;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

226. Invert Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        auto tmp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = tmp;
        return root;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 686 Reading time ≈ 1 mins.

198. House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); ++i)
        {
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp.back();
    }
};

T(n) : O(n)
S(n) : O(n)

注意到每次只用到dp[i - 2]和dp[i - 1],用2变量优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        int dp[2];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); ++i)
        {
            dp[0] = max(nums[i] + dp[0], dp[1]);
            swap(dp[0], dp[1]);
        }
        return dp[1];
    }
};

T(n) : O(n)
S(n) : O(1)

dicussion中的动态规划推导步骤

Posted on Edited on In Disqus:
Symbols count in article: 2.6k Reading time ≈ 2 mins.

169. Majority Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> map;
        int n = nums.size() / 2;
        for(auto& num : nums)
        {
            map[num] += 1;
            if(map[num] > n)
                return num;
        }
        return 0;
    }
};

T(n) : O(n)
S(n) : O(n)

法二
1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

超过n / 2数量的元素必定会在n / 2处出现

投票法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate;
        for(auto& num : nums)
        {
            if(!count)
                candidate = num;
            
            count += (candidate == num) ? 1 : -1;
        }
        return candidate;
    }
};

每次丢弃与少数元素相同的多数元素前缀，最后存在的最多的一定是多数元素。解释如下，很棒 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Approach 6: Boyer-Moore Voting Algorithm
Intuition

If we had some way of counting instances of the majority element as +1+1 and instances of any other element as -1−1, summing them would make it obvious that the majority element is indeed the majority element.

Algorithm

Essentially, what Boyer-Moore does is look for a suffix sufsuf of nums where suf[0]suf[0] is the majority element in that suffix. To do this, we maintain a count, which is incremented whenever we see an instance of our current candidate for majority element and decremented whenever we see anything else. Whenever count equals 0, we effectively forget about everything in nums up to the current index and consider the current number as the candidate for majority element. It is not immediately obvious why we can get away with forgetting prefixes of nums - consider the following examples (pipes are inserted to separate runs of nonzero count).

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

Here, the 7 at index 0 is selected to be the first candidate for majority element. count will eventually reach 0 after index 5 is processed, so the 5 at index 6 will be the next candidate. In this case, 7 is the true majority element, so by disregarding this prefix, we are ignoring an equal number of majority and minority elements - therefore, 7 will still be the majority element in the suffix formed by throwing away the first prefix.

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

Now, the majority element is 5 (we changed the last run of the array from 7s to 5s), but our first candidate is still 7. In this case, our candidate is not the true majority element, but we still cannot discard more majority elements than minority elements (this would imply that count could reach -1 before we reassign candidate, which is obviously false).

Therefore, given that it is impossible (in both cases) to discard more majority elements than minority elements, we are safe in discarding the prefix and attempting to recursively solve the majority element problem for the suffix. Eventually, a suffix will be found for which count does not hit 0, and the majority element of that suffix will necessarily be the same as the majority element of the overall array.

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

54. Spiral Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size();
        int n = matrix[0].size();
        int bL = 0, bR = n - 1, bU = 0, bB = m - 1;
        while(bL <= bR && bU <= bB)
        {
            for(int i = bL; i <= bR; ++i)
                ret.push_back(matrix[bU][i]);
            for(int i = bU + 1; i <= bB; ++i)
                ret.push_back(matrix[i][bR]);
            if(bU < bB && bL < bR)
            {
                for(int i = bR - 1; i > bL; --i)
                    ret.push_back(matrix[bB][i]);
                for(int i = bB; i > bU; --i)
                    ret.push_back(matrix[i][bL]);                
            }
            ++bL;
            --bR;
            ++bU;
            --bB;
        }
        return ret;
    }
};

螺旋

T(n) : O(n)
S(n) : O(n)

还有一种思路是把走过的路都设为障碍，每次要撞过去了就改变方向。不管如何，就是直接撞过去，撞到就变向，四个方向依次变 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return {};
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> visisted(n, vector<int>(m, 0));
        int d[4][4]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dr = 0;
        vector<int> ret;
        int i = 0, j = 0;
        while(1)
        {
            int nexti = i + d[dr][0];
            int nextj = j + d[dr][1];
            if(nexti < 0 || nextj < 0 || nexti >= n || nextj >= m || visisted[nexti][nextj])
                dr = (dr + 1) % 4;
            ret.push_back(matrix[i][j]);
            visisted[i][j] = 1;
            i += d[dr][0];
            j += d[dr][1];
            if(ret.size() == m * n)
                break;
        }
        return ret;
    }
};
T(n) : O(n)
S(n) : O(n * m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int dirs[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0;
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = 0;
        vector<int> ret;
        ret.reserve(m * n);
        while(ret.size() < m * n)
        {
            ret.push_back(matrix[i][j]);
            matrix[i][j] = 101;
            int nextI = i + dirs[d][0];
            int nextJ = j + dirs[d][1];
            if(nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n || matrix[nextI][nextJ] == 101)
                d = (d + 1) % 4;
            i += dirs[d][0];
            j += dirs[d][1];
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

199. Binary Tree Right Side View

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root)
            return {};
        vector<int> ret;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            ret.push_back(q.back()->val);
            for(int i = 0, sz = q.size(); i < sz; ++i)
            {
                auto p = q.front();
                q.pop();
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
        }
        return ret;
    }
};

T(n) : O(n) S(n) : O(k)(k为每层数)

discussion的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ret;
        rightView(ret, root, 0);
        return ret;
    }
private:
    void rightView(vector<int>& ret, TreeNode* node, int depth)
    {
        if(!node)
            return;
        
        if(depth == ret.size()) // 如果当depth != ret.size()时return，则会导致传递的终止，不行，当不等时候，那就继续遍历下去，说不定下面一层又轮到你了
            ret.push_back(node->val);
        
        rightView(ret, node->right, depth + 1);
        rightView(ret, node->left, depth + 1);
    }
};

O(logn) 总体思路是每层只添加一个，然后仅当每层没添加时才会添加进去，而层数通过ret的大小来判定，由于是从右到左遍历，因此每层添加的一定是最右的

Posted on Edited on In Disqus:
Symbols count in article: 687 Reading time ≈ 1 mins.

66. Plus One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i = digits.size() - 1;
        int c = 0;
        ++digits[i];
        while(digits[i] > 9 && i > 0)
        {
            c = digits[i] / 10;
            digits[i] %= 10;
            --i;
            digits[i] += c;
        }
        if(digits[i] > 9)
        {
            vector<int> ret(digits.size() + 1, 0);
            ret[0] = 1;
            return ret;
        }
        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for(int i = n - 1; i >= 0; --i)
        {
            ++digits[i];
            digits[i] %= 10;
            if(digits[i] != 0)
                break;
        }
        if(digits[0] == 0)
        {
            digits.resize(n + 1, 0);
            digits[0] = 1;
        }
        return digits;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

94. Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        traversal(ret, root);
        return ret;
    }
private:
    void traversal(vector<int>& ret, TreeNode* root)
    {
        if(!root) return;
        traversal(ret, root->left);  
        ret.push_back(root->val);        
        traversal(ret, root->right);
    }
};

T(n) : O(n)
S(n) : O(n)

stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            ret.push_back(cur->val);
            cur = cur->right;
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.9k Reading time ≈ 4 mins.
backtrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[0].size(); ++j)
            {
                if(word[0] == board[i][j])
                {
                    board[i][j] -= 65;
                    if(backTrack(board, word.substr(1), i ,j))
                        return true;
                    board[i][j] += 65;
                }     
            }
        }
        return false;
    }
private:
    bool backTrack(vector<vector<char>>& board, string word, int i, int j)
    {
        if(word == "")
            return true;
        if(i > 0 && word[0] == board[i - 1][j])
        {
            board[i - 1][j] -= 65;
            if(backTrack(board, word.substr(1), i - 1, j))
                return true;
            board[i - 1][j] += 65;
        }
        if(j > 0 && word[0] == board[i][j - 1])
        {
            board[i][j - 1] -= 65;
            if(backTrack(board, word.substr(1), i, j - 1))
                return true;
            board[i][j - 1] += 65;
        }
        if(i < board.size() - 1 && word[0] == board[i + 1][j])
        {
            board[i + 1][j] -= 65;
            if(backTrack(board, word.substr(1), i + 1, j))
                return true;
            board[i + 1][j] += 65;
        }
        if(j < board[0].size() - 1 && word[0] == board[i][j + 1])
        {
            board[i][j + 1] -= 65;
            if(backTrack(board, word.substr(1), i, j + 1))
                return true;
            board[i][j + 1] += 65;
        }
        return false;
    }
};

T(n) : O(n^2)
S(n) : O(1)

一点开始搜索其周围

优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[0].size(); ++j)
            {
                if(word[0] == board[i][j])
                    if(backTrack(board, word, i ,j, 1))
                        return true;   
            }
        }
        return false;
    }
private:
    bool backTrack(vector<vector<char>>& board, string& word, int i, int j, int index)
    {
        if(index == word.size())
            return true;
        board[i][j] -= 65;
        if(i > 0 && word[index] == board[i - 1][j])
        {
            if(backTrack(board, word, i - 1, j, index + 1))
                return true;
        }
        if(j > 0 && word[index] == board[i][j - 1])
        {
            if(backTrack(board, word, i, j - 1, index + 1))
                return true;
        }
        if(i < board.size() - 1 && word[index] == board[i + 1][j])
        {
            if(backTrack(board, word, i + 1, j, index + 1))
                return true;
        }
        if(j < board[0].size() - 1 && word[index] == board[i][j + 1])
        {
            if(backTrack(board, word, i, j + 1, index + 1))
                return true;
        }
        board[i][j] += 65;
        return false;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); ++i)
            for(int j = 0; j < board[0].size(); ++j)
            {
                if(backTrack(board, i, j, word, 0))
                    return true;
            }
        return false;
    }
private:
    bool backTrack(vector<vector<char>>& board,int i, int j, string& word, int index)
    {
        if(board[i][j] < 'A')
            return false;
        if(board[i][j] == word[index])
        {
            board[i][j] -= 'A';
            bool ret = (i > 0 && backTrack(board, i - 1, j, word, index + 1))
                    || (i < board.size() - 1 && backTrack(board, i + 1, j, word, index + 1))
                    || (j > 0 && backTrack(board, i, j - 1, word, index + 1))
                    || (j < board[0].size() - 1 && backTrack(board, i, j + 1, word, index + 1))
                    || (index == word.size() - 1);
            board[i][j] += 'A';
            return ret;
        }else
            return false;
    }
};
review again
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(search(board, i, j, m, n, word, 0))
                    return true;
        return false;
    }
private:
    bool search(vector<vector<char>>& board,int i, int j, const int& m, const int& n, string& word, int index)
    {
        if(index >= word.size())
            return true;
        if(i >= m || i < 0 || j >= n || j < 0 || board[i][j] < 'A' || word[index] != board[i][j])
            return false;
        board[i][j] -= 'A';
        auto ret = search(board, i + 1, j, m, n, word, index + 1)
                || search(board, i - 1, j, m, n, word, index + 1)
                || search(board, i, j + 1, m, n, word, index + 1)
                || search(board, i, j - 1, m, n, word, index + 1);
        board[i][j] += 'A';
        return ret;
    }
};

注意，字符串不能从后往前，不然不知道为什么会超时