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;
    }