Table of Contents
Find Unique Binary String
Source
Description
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.
Example 1
Input: nums = [“01″,”10”]
Output: “11”
Explanation: “11” does not appear in nums. “00” would also be correct.
Example 2
Input: nums = [“00″,”01”]
Output: “11”
Explanation: “11” does not appear in nums. “10” would also be correct.
Example 3
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’.
- All the strings of nums are unique.
Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public String findDifferentBinaryString(String[] nums) { Set<String> set = new HashSet<>(); for(String s: nums){ set.add(s); } return dfs(nums.length, set, ""); } private String dfs(int n, Set<String> exist, String s){ if(n == 0){ //check if the string exists if(!exist.contains(s)) return s; return null; } int[] x= {0, 1}; for(int i=0;i<x.length;i++){ String a; //append x[i] to the string if((a = dfs(n-1, exist, s+x[i]))!=null){ return a; } //otherwise backtrack } return null; } } |