leetcode—6/14

1. 分割回文串

给定一个字符串s，将s分割成一些子串，使每个子串都是回文串

返回s所有可能的分割方案

vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> temp;
        traceback(s, temp, res);
        return res;
    }
    void traceback(string s, vector<string>& temp, vector<vector<string>>& res)
    {
        if(s.length() == 0)
        {
            res.push_back(temp);
            return;
        }
        for(int i = 1; i <= s.length(); i++)
        {
            string s_temp = s.substr(0, i);
            if(check(s_temp))
            {
                temp.push_back(s_temp);
                traceback(s.substr(i, s.length() - i), temp, res);
                temp.pop_back();
            }
        }
    }
    bool check(string s)
    {
        int start = 0;
        int end = s.size() - 1;
        while(start < end)
        {
            if(s[start] == s[end])
            {
                start++;
                end--;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
           

2. 克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值val（int）和其邻居的列表（list[node]）

思路：加一个map表示数组是否访问过，如果访问过则不用新建节点，没有访问过新建一个节点

unordered_map<int, Node*> mp;
    Node* cloneGraph(Node* node) {
        int size = node -> neighbors.size();
        Node* root = new Node(node -> val, vector<Node*> {});
        mp[node -> val] = root;
        for(int i = 0; i < size; i++)
        {
            if(mp.count(node -> neighbors[i] -> val) == 0)
            {
                root -> neighbors.push_back(cloneGraph(node -> neighbors[i]));
            }
            else
            {
                root -> neighbors.push_back(mp[node -> neighbors[i] -> val]);
            }
        }
        return root;
    }