|
| 1 | +/* |
| 2 | + This class implements a solution to find a binary string that differs from a given list of binary strings. |
| 3 | +
|
| 4 | + Approach: |
| 5 | + 1. Define a backtrack function to explore all possible binary strings of the same length as the input strings. |
| 6 | + 2. Use a set to store the input strings to efficiently check for duplicates. |
| 7 | + 3. Backtrack through all possible binary strings of length equal to the input strings. |
| 8 | + 4. If a binary string is found that does not exist in the set of input strings, update the result and return. |
| 9 | +
|
| 10 | + Variables: |
| 11 | + - result: Holds the result, initialized to an empty string. |
| 12 | + - backtrack(): Recursive function to generate binary strings and check for uniqueness. |
| 13 | + - inputStrings: Input vector of binary strings. |
| 14 | + - currentString: Current binary string being constructed during backtracking. |
| 15 | + - stringLength: Length of binary strings in the input. |
| 16 | + - stringSet: Set to store input binary strings for fast duplicate checking. |
| 17 | +
|
| 18 | + Time Complexity: O(2^N * N), where N is the length of the binary strings. |
| 19 | + - The function 'backtrack' explores all possible binary strings of length N, which is O(2^N). |
| 20 | + - Checking for uniqueness in the set takes O(1) time on average. |
| 21 | + Space Complexity: O(2^N * N) considering the space required to store the generated binary strings during backtracking. |
| 22 | +*/ |
| 23 | + |
| 24 | +classSolution { |
| 25 | +public: |
| 26 | + string result =""; |
| 27 | + |
| 28 | +voidbacktrack(vector<string>& inputStrings, string& currentString,int stringLength, set<string>& stringSet) { |
| 29 | +if (!result.empty())return; |
| 30 | +if (currentString.size() == stringLength && stringSet.find(currentString) == stringSet.end()) { |
| 31 | + result = currentString; |
| 32 | +return; |
| 33 | + } |
| 34 | +if (currentString.size() > stringLength)return; |
| 35 | + |
| 36 | +for (char ch ='0'; ch <='1'; ++ch) { |
| 37 | + currentString.push_back(ch); |
| 38 | +backtrack(inputStrings, currentString, stringLength, stringSet); |
| 39 | + currentString.pop_back(); |
| 40 | + } |
| 41 | + } |
| 42 | + |
| 43 | + stringfindDifferentBinaryString(vector<string>& inputStrings) { |
| 44 | +int stringLength = inputStrings[0].size(); |
| 45 | + string currentString =""; |
| 46 | + set<string>stringSet(inputStrings.begin(), inputStrings.end()); |
| 47 | + |
| 48 | +backtrack(inputStrings, currentString, stringLength, stringSet); |
| 49 | +return result; |
| 50 | + } |
| 51 | +}; |