Strobogrammatic number in Java
A strobogrammatic number is an interesting mathematical concept that includes numbers that remain unchanged when they are rotated by 180 degrees. Specifically, these numbers can be viewed as having a mirrored copy of themselves inverted. The set of strobogrammatic numbers is very limited, and the few examples that exist comprise 0, 1, and 8. Interestingly, numbers 6 and 9 also have a strobogrammatic property, upside down.
Example 1:
Input
191
Output
False
Explanation
On rotating ‘191’ by 180 degrees, ‘161’ will be formed. So ‘191’ is not a strobogrammatic number.
Example 2:
Input
8008
Output
True
Explanation
Test Case 2: On rotating ‘8008’ by 180 degrees, ‘8008’ will be obtained. So ‘8008’ is a strobogrammatic number.
Approach 1: Two-pointer approach with a HashMap
The two-pointer approach combined with a HashMap is a powerful technique used to efficiently check if a given string is a Strobogrammatic number in Java. Strobogrammatic numbers are unique in that they remain unchanged when rotated 180 degrees and also this specific property allows for the creation of pairs of digits that exhibit rotational symmetry. The two-pointer approach, coupled with a HashMap to store valid Strobogrammatic pairs, is a robust and intuitive strategy for validating these numbers.
Algorithm
Step 1: Take a string n as input and check if the input string is null or empty. If true, return true since an empty string is considered Strobogrammatic.
Step 2: Create a HashMap map to store Strobogrammatic pairs. Initialize map with the following key-value pairs: '0' maps to '0', '1' maps to '1', '8' maps to '8', '6' maps to '9', '9' maps to '6'
Step 3: Two-Pointer Traversal: Initialize two pointers, left and right, at the start and end of the string, respectively.
Step 4: While left is less than or equal to right: Check if the character at the right position is a key in the map: If not, return false since it is not a valid Strobogrammatic pair.
Step 5: Check if the character at the left position is not equal to the value in the map corresponding to the character at the right position: If true, return false as the pair is not Strobogrammatic. Move the left pointer to the right and the right pointer to the left.
Step 6: If the loop completes without returning false, return true as the entire string is Strobogrammatic.
Filename: StrobogrammaticChecker.java
import java.util.HashMap;
import java.util.Map;
public class StrobogrammaticChecker {
public static void main(String[] args) {
// Example usage
String input = "9006";
System.out.println("Is " + input + " Strobogrammatic? " + isStrobogrammatic(input));
}
public static boolean isStrobogrammatic(String n) {
// Check for null or empty string
if (n == null || n.length() == 0) {
return true;
}
// Create a HashMap to store Strobogrammatic pairs
Map<Character, Character> map = new HashMap<>();
map.put('0', '0');
map.put('1', '1');
map.put('8', '8');
map.put('6', '9');
map.put('9', '6');
// Use two pointers to traverse the string from both ends
int left = 0;
int right = n.length() - 1;
// Continue until the left pointer is less than or equal to the right pointer
while (left <= right) {
// Check if the characters at the current positions are valid Strobogrammatic pairs
if (!map.containsKey(n.charAt(right)) || n.charAt(left) != map.get(n.charAt(right))) {
return false;
}
// Move the pointers towards the center
left++;
right--;
}
// If the loop completes, the string is Strobogrammatic
return true;
}
}
Output:
Is 9006 Strobogrammatic? true
Time Complexity
The time complexity of the algorithm is O(N), where N is the length of the input string. The algorithm traverses the string once using the two-pointer approach, and the number of operations performed is directly proportional to the length of the input string. Each iteration of the loop involves constant time operations, such as hashmap lookups and comparisons.
Space Complexity
The space complexity of the algorithm is O(1), constant space. The primary reason for this is that the space required for the hashmap (map) is fixed and independent of the input size. The hashmap has a constant number of key-value pairs, regardless of the length of the input string.
Approach 2: Using ArrayList
The approach using ArrayList for checking Strobogrammatic numbers involves dynamically storing and validating pairs of characters in an ArrayList. In this approach we have a more flexible and extensible solution, as the list of valid Strobogrammatic pairs can be easily modified or extended without altering the core logic of the algorithm.
Algorithm
Step 1: Take a string n as input and check if the input string is null or empty. If true, return true since an empty string is considered Strobogrammatic.
Step 2: Create ArrayList for Pairs (pairs): Initialize an ArrayList> named pairs to store Strobogrammatic pairs dynamically. Populate pairs with predefined pairs: '00', '11', '88', '69', and '96'.
Step 3: Initialize two pointers, left and right, at the start and end of the string, respectively. While left is less than or equal to right: Obtain the characters at the current positions, leftChar and rightChar.
Step 4: Check if the pair (leftChar, rightChar) is a valid Strobogrammatic pair using the isValidPair method. If not, return false.
Step 5: Validation Method (isValidPair): Accept two characters (leftChar and rightChar) and the pairs ArrayList as input. Check if the pair (leftChar, rightChar) or (rightChar, leftChar) matches any pair in pairs.
Step 6: If a match is found, return true. If no match is found, return false. If the loop completes without returning false, return true as the entire string is Strobogrammatic.
Filename: StrobogrammaticCheckerAL.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class StrobogrammaticCheckerAL {
public static void main(String[] args) {
// Example usage
String input = "191";
System.out.println("Is " + input + " Strobogrammatic? " + isStrobogrammatic(input));
}
public static boolean isStrobogrammatic(String n) {
// Check for null or empty string
if (n == null || n.length() == 0) {
return true; // An empty string is considered Strobogrammatic
}
// Create an ArrayList to store Strobogrammatic pairs
List<List<Character>> pairs = new ArrayList<>(Arrays.asList(
Arrays.asList('0', '0'),
Arrays.asList('1', '1'),
Arrays.asList('8', '8'),
Arrays.asList('6', '9'),
Arrays.asList('9', '6')
));
// Use two pointers to traverse the string from both ends
int left = 0;
int right = n.length() - 1;
// Continue until the left pointer is less than or equal to the right pointer
while (left <= right) {
// Check if the characters at the current positions are valid Strobogrammatic pairs
char leftChar = n.charAt(left);
char rightChar = n.charAt(right);
if (!isValidPair(leftChar, rightChar, pairs)) {
return false;
}
// Move the pointers towards the center
left++;
right--;
}
// If the loop completes, the string is Strobogrammatic
return true;
}
private static boolean isValidPair(char leftChar, char rightChar, List<List<Character>> pairs) {
for (List<Character> pair : pairs) {
if ((pair.get(0) == leftChar && pair.get(1) == rightChar) ||
(pair.get(0) == rightChar && pair.get(1) == leftChar)) {
return true;
}
}
return false;
}
}
Output:
Is 191 Strobogrammatic? false
Time Complexity
The time complexity of the algorithm is O(N), where N is the length of the input string. The algorithm traverses the string once using the two-pointer approach, and the number of operations performed is directly proportional to the length of the input string. Each iteration of the loop involves constant time operations, such as array lookups and comparisons, and the loop runs until the pointers meet at the center.
Space Complexity
The space complexity of the algorithm is O(1). Although there is an ArrayList (pairs) used for storing the Strobogrammatic pairs, the size of this ArrayList is constant and does not depend on the input size. It remains the same regardless of the length of the input string.
Approach 3: Dynamic Programming
The Dynamic Programming approach for checking Strobogrammatic numbers involves the use of recursion and memorization to efficiently generate Strobogrammatic numbers of a given length. By building the solutions for smaller subproblems and storing them in a memorization table, the algorithm avoids redundant computations, improving both time and space complexity.
Algorithm
Step 1: Take a string n as input and check if the input string is null or empty. If true, return true since an empty string is considered Strobogrammatic.
Step 2: Dynamic Programming Setup: Create a memorization table, represented by a HashMap> named memo, to store solutions for subproblems.
Step 3: Generate Strobogrammatic Numbers: Call the generateStrobogrammatic method, passing the length of the input string. The method generateStrobogrammatic internally calls the recursive helper method generateStrobogrammaticHelper.
Step 4: Recursive Helper (generateStrobogrammaticHelper): If the memoization table contains the solution for the given length (n), return the stored result.
Step 5: If n is 0, return a list containing an empty string. If n is 1, return a list containing "0," "1," and "8." Recursively call generateStrobogrammaticHelper for n-2 to obtain solutions for smaller subproblems.
Step 6: Build Strobogrammatic numbers of length n by appending digits to the left and right of solutions for smaller subproblems. Store the result in the memoization table and return the generated Strobogrammatic numbers.
Step 7: Check for Strobogrammaticity: Check if the input string is present in the list of generated Strobogrammatic numbers. Return true if the input string is found; otherwise, return false.
Filename: StrobogrammaticCheckerDP.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class StrobogrammaticCheckerDP {
public static void main(String[] args) {
// Example usage
String input = "8008";
System.out.println("Is " + input + " Strobogrammatic? " + isStrobogrammatic(input));
}
public static boolean isStrobogrammatic(String n) {
// Check for null or empty string
if (n == null || n.length() == 0) {
return true; // An empty string is considered Strobogrammatic
}
// Use dynamic programming to generate Strobogrammatic numbers
List<String> strobogrammaticNumbers = generateStrobogrammatic(n.length());
// Check if the input string is in the list of generated numbers
return strobogrammaticNumbers.contains(n);
}
private static List<String> generateStrobogrammatic(int n) {
return generateStrobogrammaticHelper(n, n);
}
private static List<String> generateStrobogrammaticHelper(int current, int n) {
if (current == 0) {
return Arrays.asList("");
}
if (current == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> result = new ArrayList<>();
List<String> subResult = generateStrobogrammaticHelper(current - 2, n);
for (String s : subResult) {
if (current != n) {
result.add("0" + s + "0");
}
result.add("1" + s + "1");
result.add("6" + s + "9");
result.add("8" + s + "8");
result.add("9" + s + "6");
}
return result;
}
}
Output:
Is 8008 Strobogrammatic? true
Time Complexity
The time complexity of the provided Dynamic Programming approach is O(5^(N/2)), where N is the length of the input string. The branching factor is 5 (for the five possible digits at each position: 0, 1, 6, 8, 9), and the depth of recursion is proportional to N/2, where N is the length of the input string.
Space Complexity
The space complexity of the algorithm is O(5^(N/2)), which is dominated by the memorization table, which stores the solutions for subproblems. In the worst case, the memorization table can have entries for all possible subproblems of length n. Since the branching factor is 5, and the depth of recursion is proportional to N/2, the space complexity becomes exponential.
Approach 4: Using a HashSet
The approach using a HashSet for checking Strobogrammatic numbers involves using a HashSet to store valid pairs of characters that form Strobogrammatic numbers. This HashSet provides constant-time lookups, allowing for efficient validation of pairs during the traversal of the input string.
Algorithm
Step 1: Take a string n as input and check if the input string is null or empty. If true, return true since an empty string is considered Strobogrammatic.
Step 2: Create a HashSet named strobogrammaticPairs to store valid Strobogrammatic pairs: "00", "11", "88", "69", and "96".
Step 3: Use two pointers (left and right) to iterate through the input string from both ends. Continue until the left pointer is less than or equal to the right pointer.
Step 4: For each pair of characters at positions left and right, construct a string (currentPair). Check if currentPair is present in the HashSet of valid Strobogrammatic pairs (strobogrammaticPairs). If not, return false as the input string is not a Strobogrammatic number.
Step 5: If the traversal completes without finding any invalid pairs, return true. The input string is a Strobogrammatic number.
Filename: StrobogrammaticCheckerHS.java
import java.util.HashSet;
import java.util.Set;
public class StrobogrammaticCheckerHS {
public static void main(String[] args) {
// Example usage
String input = "9006";
System.out.println("Is " + input + " Strobogrammatic? " + isStrobogrammatic(input));
}
public static boolean isStrobogrammatic(String n) {
// Check for null or empty string
if (n == null || n.length() == 0) {
return true; // An empty string is considered Strobogrammatic
}
// Valid Strobogrammatic pairs
Set<String> strobogrammaticPairs = new HashSet<>();
strobogrammaticPairs.add("00");
strobogrammaticPairs.add("11");
strobogrammaticPairs.add("88");
strobogrammaticPairs.add("69");
strobogrammaticPairs.add("96");
// Use two pointers to traverse the string from both ends
int left = 0;
int right = n.length() - 1;
// Continue until the left pointer is less than or equal to the right pointer
while (left <= right) {
// Check if the characters at the current positions form a valid Strobogrammatic pair
String currentPair = "" + n.charAt(left) + n.charAt(right);
if (!strobogrammaticPairs.contains(currentPair)) {
return false;
}
// Move the pointers towards the center
left++;
right--;
}
// If the loop completes, the string is Strobogrammatic
return true;
}
}
Output:
Is 9006 Strobogrammatic? true
Time Complexity
The time complexity of the HashSet approach for checking Strobogrammatic numbers is O(N), where N is the length of the input string. The algorithm iterates through the string using two pointers, comparing characters at corresponding positions.
Space Complexity
The space complexity is O(1), the primary data structure used is the HashSet strobogrammaticPairs, which has a constant number of elements (five valid pairs: "00", "11", "88", "69", and "96"). The space required for the HashSet is constant, independent of the input size.
Approach 5: Stack-based Approach
The stack-based approach for checking Strobogrammatic numbers is a strategy that involves utilizing a stack data structure to track and validate characters during the traversal of the input string. This approach leverages the Last-In-First-Out (LIFO) nature of a stack, making it a suitable choice for efficiently managing pairs of characters at corresponding positions in the string.
Algorithm
Step 1: Take a string n as input and check if the input string is null or empty. If true, return true since an empty string is considered Strobogrammatic.
Step 2: Define a string pair containing valid Strobogrammatic pairs: "00", "11", "88", "69", and "96" and create a stack (Stack stack) to keep track of characters during the traversal of the input string.
Step 3: Traverse the String with Two Pointers: Use two pointers (left and right) to iterate through the input string from both ends. Iterate through the characters of the input string. Push each character onto the stack.
Step 4: For each pair of characters at corresponding positions: Form a string currentPair by popping a character from the stack and combining it with the character at position left.
Step 5: Check if currentPair is present in the string of valid Strobogrammatic pairs (pairs). If not, return false as the input string is not a Strobogrammatic number.
Step 6: If the traversal completes without finding any invalid pairs, return true. The input string is a Strobogrammatic number.
Filename: StrobogrammaticCheckerStack.java
import java.util.Stack;
public class StrobogrammaticCheckerStack {
public static void main(String[] args) {
// Example usage
String input = "8008";
System.out.println("Is " + input + " Strobogrammatic? " + isStrobogrammatic(input));
}
public static boolean isStrobogrammatic(String n) {
// Check for null or empty string
if (n == null || n.length() == 0) {
return true; // An empty string is considered Strobogrammatic
}
// Valid Strobogrammatic pairs
String pairs = "00 11 88 69 96";
// Use a stack to track characters during traversal
Stack<Character> stack = new Stack<>();
// Iterate through the characters of the input string
for (char c : n.toCharArray()) {
// Push each character onto the stack
stack.push(c);
}
// Use two pointers to traverse the string from both ends
int left = 0;
int right = n.length() - 1;
// Continue until the left pointer is less than or equal to the right pointer
while (left <= right) {
// Check if the characters at the current positions form a valid Strobogrammatic pair
String currentPair = "" + stack.pop() + n.charAt(left);
if (!pairs.contains(currentPair)) {
return false;
}
// Move the left pointer towards the center
left++;
}
// If the loop completes, the string is Strobogrammatic
return true;
}
}
Output:
Is 8008 Strobogrammatic? true
Time Complexity
The time complexity of the stack-based approach for checking Strobogrammatic numbers is O(N), where N is the length of the input string. The algorithm iterates through the string linearly using two pointers, comparing characters at corresponding positions.
Space Complexity
The space complexity is O(N/2) in the worst case. The primary data structure used is the stack (Stack<Character> stack), which stores approximately half of the characters in the input string. The space required for the stack is proportional to half the length of the input string.
Conclusion
In conclusion, the Strobogrammatic number problem in Java can be approached using various strategies. In practice, the HashMap or HashSet approaches are often preferred for their simplicity and constant-time lookups. The Stack-based approach, while valid, introduces additional space complexity proportional to the input size.