712266. Generate all binary strings
Medium
Generate all binary strings
Slug: generate-all-binary-strings
Difficulty: Medium
Id: 712266
Summary
Generate all possible binary strings with a given length. The problem involves creating an algorithm to generate all combinations of 0s and 1s for a specified number of bits.
Detailed Explanation
The approach to solve this problem is simple. We can use recursion to generate all binary strings. The idea is to consider each bit in the string as either 0 or 1, and then recursively generate all possible strings for the remaining bits.
Here's a step-by-step breakdown of the solution:
- Start with an empty string.
- For each bit in the desired length:
- Add '0' to the current string (generate all binary strings for the remaining bits).
- Add '1' to the current string (generate all binary strings for the remaining bits).
- Return the list of generated binary strings.
Time and Space Complexity
The time complexity is O(2^n), where n is the desired length, because we're generating all possible combinations. The space complexity is also O(n) as we need to store each binary string in memory.
Optimized Solutions
Java
import java.util.ArrayList;
import java.util.List;
public class GenerateBinaryStrings {
public static List<String> generate(int n) {
List<String> result = new ArrayList<>();
generate("", n, result);
return result;
}
private static void generate(String s, int n, List<String> result) {
if (n == 0) {
result.add(s);
} else {
generate(s + "0", n - 1, result);
generate(s + "1", n - 1, result);
}
}
public static void main(String[] args) {
List<String> binaryStrings = generate(3);
for (String binaryString : binaryStrings) {
System.out.println(binaryString);
}
}
}