*138. 随机链表的复制
用哈希表记录当前创建的节点的后继节点和指向的节点是否被创建，若未被创建，则递归地创建，拷贝完成后，然后再回溯到当前创建的节点，继续另一个节点（后继节点或指向的节点）的内容
unordered_map的count()用于检查某个元素是否在表里
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> nodeMap;
Node* copyRandomList(Node* head) {
if(head==nullptr)
return nullptr;
if(!nodeMap.count(head))
{
Node* head1 = new Node(head->val);
nodeMap[head] = head1;
head1->next = copyRandomList(head->next);
head1->random = copyRandomList(head->random);
}
return nodeMap[head];
}
};
139.单词拆分
动态规划+剪枝
检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断
dp[i]:以 i 结尾的字符串是否可以被 wordDict 中的单词组合而成
相当于完全背包问题
字符串是背包，wordDict 中的单词是不同重量的物品
外层循环遍历背包容量，即遍历wordDict 中每个单词长度
内层循环遍历wordDict 中的每个单词，看是否匹配
因此定义dp数组为bool类型
vector<bool> dp(s.size() + 1);
定义边界条件dp[0]=true;
dp[i]=dp[i] || dp[i-word.size()]
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size() + 1);
dp[0] = true;
for(int i = 1; i < s.size()+1; i++){
for(auto& word: wordDict){
int sz = word.size();
if (i - sz >= 0 && s.substr(i - sz, sz) == word)
dp[i] = dp[i] || dp[i - sz];
}
}
return dp[s.size()];
}
};