Cinte's Leetcode Record

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        backTrack(nums, target, 0, 0);
        return ret;
    }
private:
    int ret = 0;
    void backTrack(vector<int>& nums, int target, int cur, int i)
    {
        if(i >= nums.size())
        {
            if(cur == target)
                ++ret;
            return;
        }
        backTrack(nums, target, cur + nums[i], i + 1);
        backTrack(nums, target, cur - nums[i], i + 1);
    }      
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        map[nums[0]] += 1;
        map[-nums[0]] += 1;
        for(int i = 1; i < nums.size(); ++i)
        {
            unordered_map<int, int> tmp;
            for(auto& it : map)
            {
                tmp[it.first + nums[i]] += it.second;
                tmp[it.first - nums[i]] += it.second;
            }
            map = tmp;
        }
        return map[target];
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int diff = accumulate(nums.begin(), nums.end(), 0) - target;
        if(diff < 0 || diff & 1)
            return 0;
        int neg = diff >> 1;
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            int num = nums[i - 1];
            for(int j = 0; j <= neg; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(num <= j)
                    dp[i][j] += dp[i - 1][j - num];
            }
        }
        return dp[n][neg];
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int diff = accumulate(nums.begin(), nums.end(), 0) - target;
        if(diff < 0 || diff & 1)
            return 0;
        int neg = diff >> 1;
        int n = nums.size();
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            int num = nums[i - 1];
            for(int j = neg; j >= 0; --j)
            {
                dp[j] = dp[j];
                if(num <= j)
                    dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
};

/**
 * 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 pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        stack<TreeNode*> q;
        q.push(root);
        int count = 0;
        int cur = 0;
        while(!q.empty())
        {
            auto p = q.top();
            q.pop();
            backTrack(p, targetSum, cur, count);
            if(p->left)
                q.push(p->left);
            if(p->right)
                q.push(p->right);
        }
        return count;
    }
private:
    void backTrack(TreeNode* root, int target, int& cur, int& count)
    {
        if(!root)
            return;
        cur += root->val;
        if(cur == target)
            ++count;
        backTrack(root->left, target, cur, count);
        backTrack(root->right, target, cur, count);
        cur -= root->val;
    }
};

/**
 * 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 pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        cur += root->val; // 加上当前值，开始遍历他的儿子
        int ret = map[cur - targetSum]; // 如果存在在他回溯的路径上存在cur-targetSum的值，说明存在这样一个节点使得在此节点之前的和为cur-targetSum。如果路径上存在多条和为此，那么后面也和他的路径数量相同。
        ++map[cur]; // 路径当前和所对应的计数加一。可处理存在重复和的情况。
        ret += pathSum(root->left, targetSum) + pathSum(root->right, targetSum); // 往儿子遍历，如果儿子中也存在这样的路径，那就加上去。
        --map[cur]; // 回溯返回
        cur -= root->val; // 回溯返回
        return ret; // 返回这个节点到他儿子路上和为target的路径数
    }
private:
    unordered_map<int, int> map{{0, 1}};
    int cur = 0;
};

/**
 * 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 pathSum(TreeNode* root, int targetSum) {
        unordered_map<int, int> map;
        map[0] = 1;
        recurse(root, map, targetSum, 0);
        return ret;
    }
private:
    int ret = 0;
    void recurse(TreeNode* root, unordered_map<int, int>& map, int targetSum, int curSum)
    {
        if(!root)
            return;
        curSum += root->val;
        ret += map[curSum - targetSum]; // 注意这两行的顺序，大坑啊
        ++map[curSum];                  // 如果++在前的话，假如targetSum = 0，那就每个节点都会算上自己了，对于targetSum不是0的情况似乎没什么影响
        recurse(root->left, map, targetSum, curSum);
        recurse(root->right, map, targetSum, curSum);
        --map[curSum];
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(!travesalChilds(word, start, point))
            {
                point->childs.push_back(new Node(word[start]));
                point = point->childs.back(); 
            }
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(!travesalChilds(word, start, point))
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(!travesalChilds(prefix, start, point))
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        vector<Node*> childs;
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
    bool travesalChilds(string& s, int& start, Node*& node)
    {
        for(auto& child : node->childs)
        {
            if(child->val == s[start])
            {
                node = child;
                return true;
            }
        }
        return false;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(point->childs.find(word[start]) != point->childs.end())
                point = point->childs[word[start]];
            else
                point = point->childs.insert({word[start] ,new Node(word[start])}).first->second;
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(point->childs.find(word[start]) != point->childs.end())
                point = point->childs[word[start]];
            else
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(point->childs.find(prefix[start]) != point->childs.end())
                point = point->childs[prefix[start]];
            else
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        unordered_map<char ,Node*> childs;
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(point->childs[word[start] - 'a'] != nullptr)
                point = point->childs[word[start] - 'a'];
            else
            {
                point->childs[word[start] - 'a'] = new Node(word[start]);
                point = point->childs[word[start] - 'a'];
            }
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(point->childs[word[start] - 'a'] != nullptr)
                point = point->childs[word[start] - 'a'];
            else
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(point->childs[prefix[start] - 'a'] != nullptr)
                point = point->childs[prefix[start] - 'a'];
            else
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        Node* childs[26]{ nullptr };
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

class Trie {
public:
    Trie() : head(new Node()) {

    }
    
    void insert(string word) {
        auto point = head;
        for(auto ch : word)
        {
            if(!point->childs[ch - 'a'])
                point->childs[ch - 'a'] = new Node();
            point = point->childs[ch - 'a'];
        }
        point->isWord = true;
    }
    
    bool search(string word) {
        auto point = head;
        for(auto ch : word)
        {
            if(!point->childs[ch - 'a'])
                return false;
            point = point->childs[ch - 'a'];
        }
        return point->isWord;
    }
    
    bool startsWith(string prefix) {
        auto point = head;
        for(auto ch : prefix)
        {
            if(!point->childs[ch - 'a'])
                return false;
            point = point->childs[ch - 'a'];
        }
        return true;
    }
private:
    struct Node
    {
        Node* childs[26]{};
        bool isWord;
        Node() : isWord(false) {}
    };
private:
    Node *head;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

/**
 * 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 rob(TreeNode* root) {
        auto ret = helper(root);
        return max(ret.first, ret.second);
    }
private:
    pair<int, int> helper(TreeNode* node)
    {
        if(!node)
            return {0, 0};
        
        auto left = helper(node->left);
        auto right = helper(node->right);
        
        // if rob
        int rob = node->val + left.second + right.second;
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        
        return {rob, notRob};
    }
};

/**
 * 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 rob(TreeNode* root) {
        return max(helper(root, false), helper(root, true));
    }
private:
    unordered_map<TreeNode*, int> robed;
    unordered_map<TreeNode*, int> noRobed;
    int helper(TreeNode* node, bool isRobed)
    {
        if(!node)
            return 0;
        if(isRobed)
        {
            if(robed.find(node) != robed.end())
                return robed[node];
            else
            {
                int left = helper(node->left, false);
                int right = helper(node->right, false);
                int ret = node->val + left + right;
                robed[node] = ret;
                return ret;
            }
        }else
        {
            if(noRobed.find(node) != noRobed.end())
                return noRobed[node];
            else
            {
                int left = max(helper(node->left, false), helper(node->left, true));
                int right = max(helper(node->right, false), helper(node->right, true));
                int ret = left + right;
                noRobed[node] = ret;
                return ret;
            }
        }
    }
};

/**
 * 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 rob(TreeNode* root) {
        unordered_map<int, vector<int>> pc;
        vector<int> val; // vector来存放节点的值
        queue<TreeNode*> qNode; // 用来遍历
        queue<int> qIndex; // 用来存放节点所对应的指标
        int index = -1;
        qNode.push(root);
        qIndex.push(index);
        // 将所有节点的值放入val，每个节点对应index
        while(!qNode.empty())
        {
            // 层级遍历
            auto node = qNode.front();
            qNode.pop();
            auto fatherI = qIndex.front();
            qIndex.pop();
            if(node)
            {
                ++index;
                pc[fatherI].push_back(index); // father中放入孩子
                val.push_back(node->val);
                qNode.push(node->left);
                qNode.push(node->right);
                qIndex.push(index);
                qIndex.push(index);
            }
        }
        
        // 开始dp
        vector<int> dpRob(index + 1);
        vector<int> dpNoRob(index + 1);
        
        // 从最后一层开始往上走
        for(int i = index; i >= 0; --i)
        {
            if(pc[i].empty()) // 叶子节点的情况
            {
                dpRob[i] = val[i];
                dpNoRob[i] = 0;
            }else
            {
                dpRob[i] = val[i];
                // 遍历孩子节点
                for(auto& j : pc[i])
                {
                    dpRob[i] += dpNoRob[j]; // 如果rob，那么就加上前面不rob的
                    dpNoRob[i] += max(dpRob[j], dpNoRob[j]); // 如果不rob，那么前面随便rob还是不rob，取最大值
                }
            }
        }
        return max(dpRob[0], dpNoRob[0]);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        pair<int, int> maxp{0, 1};
        int maxlen = 1;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for(int i = 0; i < s.size(); ++i)
            dp[i][i] = true;
        for(int i = 0; i < s.size() - 1; ++i)
        {
            dp[i][i + 1] = (s[i] == s[i + 1]);
            if(dp[i][i + 1] && maxlen < 2)
            {
                maxlen = 2;
                maxp = pair<int, int>{i, 2};
            }
        }
        
        // 此处循环先j再i 是由于以下j为j - 1 而 i 为 i + 1
        // 如果先i 再 j，则i + 1永远不是i的前一任
        // 先j后i，则可以用i,i+1的base来处理
        // 也是不断拉长区间
        for(int j = 1; j < s.size(); ++j)
        {
            for(int i = 0; i < j; ++i)
            {
                if(i == j || j == i + 1)
                    continue;
                dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
                if(dp[i][j])
                {
                    maxp = j - i + 1 > maxlen ? pair<int, int>{i, j - i + 1} : maxp;   
                    maxlen = max(maxlen, maxp.second);
                }
            }
        }
        return s.substr(maxp.first, maxp.second);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int m = s.size();
        vector<vector<bool>> dp(m, vector<bool>(m, false));
        int start{ 0 }, maxLength{ 1 };
        for(int i = 0; i < m; ++i)
            dp[i][i] = true;
        for(int i = 0; i < m - 1; ++i)
            if((dp[i][i + 1] = s[i] == s[i + 1]) && (maxLength = 2))
                start = i;
        for(int len = 3; len <= m; ++len)
        {
            for(int i = 0, j = i + len - 1; j < m; ++i, ++j)
            {
                if(dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1])
                {
                    start = i;
                    maxLength = len;
                }
            }
        }
        return s.substr(start, maxLength);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        pair<int, int> maxP;
        int maxLen = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            auto lenO = extract(s, i, i);
            auto lenS = extract(s, i, i + 1);
            if (max(lenO.second, lenS.second) > maxLen)
            {
                if (lenO.second > lenS.second)
                    maxP = lenO;
                else
                    maxP = lenS;
                maxLen = maxP.second;
            }
        }
        return s.substr(maxP.first, maxP.second);
    }
private:
    pair<int, int> extract(string& s, int left, int right)
    {
        while (left >= 0 && right <= s.size() && s[left] == s[right])
        {
            --left;
            ++right;
        }
        return pair<int, int>{left + 1, right - left - 1};
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ret = nullptr;
        backTrack(root, p, q, ret);
        return ret;
    }
private:
    bool backTrack(TreeNode* node, TreeNode* p, TreeNode* q, TreeNode*& ret)
    {
        if(!node)
            return false;
        // 设置为1的话就可以隐藏细节，仅仅那个最近的具有最丰富的细节，往上就没了，所以上面就不会再覆盖之前的结果
        int mid = (node == p || node == q) ? 1 : 0;
        int left = backTrack(node->left, p, q, ret) ? 1: 0;
        int right = backTrack(node->right, p, q, ret) ? 1 : 0;
        if(mid + left + right >= 2)
        {
            ret = node;   
        }
        return mid + left + right;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*, TreeNode*> parent;
        parent[root] = nullptr;
        stack<TreeNode*> s;
        s.push(root);
        while(parent.find(p) == parent.end() || parent.find(q) == parent.end()) // 这里不能用!parent[p] || !parent[q],因为parent[root] = nullptr
        {
            auto tmp = s.top();
            s.pop();
            if(tmp->right)
            {
                parent[tmp->right] = tmp;
                s.push(tmp->right);
            }
            if(tmp->left)
            {
                parent[tmp->left] = tmp;
                s.push(tmp->left);
            }
        }
        
        unordered_set<TreeNode*> ancestor;
        while(parent.find(p) != parent.end())
        {
            ancestor.insert(p);
            p = parent[p];
        }
        
        while(ancestor.find(q) == ancestor.end())
        {
            q = parent[q];
        }
        return q;
    }    
};

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i)
        {
            for(int j = 0; j < coins.size(); ++j)
            {
                if(coins[j] <= i)
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> map(numCourses);
        vector<bool> done(numCourses, false); // 记录走过的点，如果走到了这个点并标记为true，表示通过这个点可以走回去
        vector<bool> todo(numCourses, false); // 记录在走路过程中走过的点，如果走路过程中撞到了，表明有环，那么必定返回false
        for(auto& course : prerequisites)
        {
            map[course[1]].push_back(course[0]); // 建立有向图,注意方向  review : 其实主要是判断环路，方向无所谓啦
        }
        for(int i = 0; i < numCourses; ++i)
        {
            if(!helper(map, i, todo, done))
                return false;
        }
        return true;
    }
private:
    bool helper(vector<vector<int>>& map, int index, vector<bool>& todo, vector<bool>& done)
    {
        if(todo[index]) // 撞到了 失败了
            return false;
        if(done[index])
            return true; // 因为如果这条路不能走的话，之前就已经返回false了，所以再次走到肯定是安全的
        
        done[index] = true; // 走了这个点
        todo[index] = true; // 走到了这个点
        for(auto& i : map[index])
        {
            if(!helper(map, i, todo, done))
            {
                return false; 
            }
        }
        todo[index] = false; // 这趟走完了，没有发现环，这条路是安全的
        return true;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> visited(numCourses, 0);
        vector<int> checked(numCourses, 0); // 0 : unknown, 1 : ok
        vector<vector<int>> graph(numCourses);
        for(auto& c : prerequisites)
            graph[c[0]].push_back(c[1]);
        for(int i = 0; i < numCourses; ++i)
            if(!check(graph, visited, checked, i))
                return false;
        return true;
    }
private:
    bool check(vector<vector<int>>& graph, vector<int>& visited, vector<int>& checked, int course)
    {
        // checked表示这些课的所有先决条件都满足
        // checked过的点是某些点的先决条件
        // 一门课可能有多个先决课，没门先决课都得学，而不是多个课选一个学
        if(checked[course])
            return true;
        // 如果这些课不在checked的列表中，那么这节课往回走的时候，注定遇上了环路。
        if(visited[course])
            return false;
        visited[course] = 1;
        for(auto& c : graph[course])
        {
            if(!check(graph, visited, checked, c))
                return false; // 这里直接不把visited复位了，因为不复位可以直接用来表示此路不通
        }
        visited[course] = 0;
        checked[course] = 1;
        return true;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = 0;
        int j = matrix[0].size() - 1;
        while(i < matrix.size() && j >= 0)
        {
            if(matrix[i][j] == target)
                return true;
            if(matrix[i][j] < target)
                ++i;
            else
                --j;
        }
        return false;
    }
};

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int maxLen = 0;
        int curLen = 1;
        bool stop = false;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(matrix[i][j] == '1')
                {
                    while(curLen + i < m && curLen + j < n && !stop)
                    {
                        for(int k = j; k <= curLen + j; ++k)
                        {
                            if(matrix[i + curLen][k] == '0')
                            {
                                stop = true;
                                break;
                            }
                        }
                        for(int k = i; k <= curLen + i; ++k)
                        {
                            if(matrix[k][j + curLen] == '0')
                            {
                                stop = true;
                                break;
                            }                            
                        }
                        if(!stop)
                            ++curLen;
                    }
                    maxLen = max(curLen, maxLen);
                    curLen = 1;
                    stop = false;
                }
            }
        }
        return maxLen * maxLen;
    }
};

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxLen = 0;
        vector<int> dp(matrix[0].size() + 1, 0);
        int prev = 0;
        for(int i = 1; i <= matrix.size(); ++i)
        {
            for(int j = 1; j <= matrix[0].size(); ++j)
            {
                int tmp = dp[j];
                if(matrix[i - 1][j - 1] == '1')
                {
                    dp[j] = min(min(dp[j - 1], dp[j]), prev) + 1;
                    maxLen = max(dp[j], maxLen);
                }else
                {
                    dp[j] = 0;
                }
                prev = tmp;
            }
        }
        return maxLen * maxLen;
    }
};