题目描述
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
Example1:
Input: nums = [“01”,”10”] Output: “11” Explanation: “11” does not appear in nums. “00” would also be correct.
Example2:
Input: nums = [“00”,”01”] Output: “11” Explanation: “11” does not appear in nums. “10” would also be correct.
Example3:
Input: nums = [“111”,”011”,”001”] Output: “101” Explanation: “101” does not appear in nums. “000”, “010”, “100”, and “110” would also be correct.
Constraints
- n == nums.length
- 1 <= n <= 16
- nums[i].length == n
- nums[i] is either ‘0’ or ‘1’.
解题思路
- 本质是字符串的全遍历+，判断给出的字符串剩下的未出现在全遍历的集合里
- 首先需要将给出的字符串放入到集合容器里
- 然后通过不断给某一位赋值，判断是否在这个容器里出现过，如果赋值到某一位的时候，发现容器里没有，此时就找到了答案
- 如果赋值到某一位的时候，发现存在了，就只能赋成原来的值（回溯的思想，先试探将某个值改变，看是否能够达到目的，如果达到了，一切ok；如果没达到，就将值改变到原来）
- 继续递归
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
set<string> sets(nums.begin(), nums.end());
string res(nums.size(), '0');
funhelper(sets, 0, res, nums.size());
return res;
}
bool funhelper(set<string>& sets, int index, string& res, int size){
if(size == index){
if(sets.count(res) == 0){
return true;
}else{
return false;
}
}
res[index] = '1';
if(funhelper(sets, index + 1, res, size)){
return true;
}
res[index] = '0';
return funhelper(sets, index + 1, res, size);
}
};
