Check if String is a Prefix of Array in Java
Checking if a string is a prefix of an array in Java involves evaluating whether the given string matches the initial elements of the array. The operation is common in various programming scenarios, such as when validating user input, searching for patterns, or handling data processing tasks.
In the context of Java, you might encounter situations where you need to determine if a specific string is a prefix of an array of strings. It could be relevant in applications like text processing, where you may want to identify if a given word or sequence of characters appears at the beginning of an array of words.
Examples:
Example 1:
Input:
String[] arr = {"baj", "mnc", "rahi", "banjo"}; Output:
No.
Explanation:
Here, the target string is "baj," and the array includes elements such as "baj," "mnc," "rahi," and "banjo·" Since the target string "baj" does not match the prefix of any other element in the array, the output is "No·"
Example 2:
Input:
String[] arr = {"bahe", "baj", "jabf", "bahej"}; Output:
Yes.
Explanation:
In this example, the target string is "bahe," and the array consists of elements like "bahe," "baj," "jabf," and "bahej·" As the target string "bahe" is a prefix of the first element "bahe" and the fourth element "bahej," the output is "Yes·"
Example 3:
Input:
String[] arr = {"book", "bookmark", "boot", "booty"}; Output:
Yes.
Explanation:
In this scenario, the target string is "book," and the array contains elements like "book," "bookmark," "boot," and "booty·" Since the target string "book" is not a prefix of any array element, the output is "No·"
Example 4:
Input:
String[] arr = {"green", "greenery", "greenhouse", "greed"}; Output:
Yes.
Explanation:
In this example, the target string is "green," and the array consists of elements like "green," "greenery," "greenhouse," and "greed·" As the target string "green" is a prefix of the first element "green," the second element "greenery," and the third element "greenhouse," the output is "Yes·"
Approach 1: Using Brute force
ALGORITHM:
Step 1: Create a method called hasPrefix that takes an array of strings (arr) as input·
Step 2: Use two nested loops to iterate over each pair of strings in the array·
Step 3: Iterate through each element in the array using the outer loop (for (int i = 0; i < arr·length; i++))·
Step 4: For each outer loop iteration, start another loop (for (int j = 0; j < arr·length; j++)) to compare the current element with all other elements in the array·
Step 5: Within the inner loop, use an if statement to check if the string at index j starts with the string at index i (arr[j]·startsWith(arr[i]))·
Step 6: Ensure that you are not comparing a string with itself by including a condition if (i != j)·
Step 7: If a matching prefix is found (if (arr[j]·startsWith(arr[i]))), return true·
Step 8: Allow both loops to complete their iterations, examining all pairs of strings in the array·
Step 9: If no matching prefixes are found, meaning the loops complete without returning true, return false after the loops·
Step 10: Close the hasPrefix method·
Step 11: In the main method, create examples (e·g·, arrays of strings) and call the hasPrefix method on each example, printing "Yes" if there is a matching prefix, and "No" otherwise·
Implementation:
The implementation of the above steps given below
FileName: StringPrefixChecker.java
import java.util.*;
public class StringPrefixChecker {
public static boolean hasPrefix(String[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
// Check if arr[i] is a prefix of arr[j]
if (i != j && arr[j].startsWith(arr[i])) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
// Example 1:
String[] arr1 = {"baj", "mnc", "rahi", "banjo"};
System.out.println("Example 1: " + (hasPrefix(arr1) ? "Yes" : "No"));
// Example 2:
String[] arr2 = {"bahe", "baj", "jabf", "bahej"};
System.out.println("Example 2: " + (hasPrefix(arr2) ? "Yes" : "No"));
// Example 3:
String[] arr3 = {"book", "bookmark", "boot", "booty"};
System.out.println("Example 3: " + (hasPrefix(arr3) ? "Yes" : "No"));
// Example 4:
String[] arr4 = {"green", "greenery", "greenhouse", "greed"};
System.out.println("Example 4: " + (hasPrefix(arr4) ? "Yes" : "No"));
}
}
Output:
Example 1: No
Example 2: Yes
Example 3: Yes
Example 4: Yes
Complexity Analysis:
Time Complexity:
The time complexity of the hasPrefix method can be expressed in Big O notation as O(n^2), where 'n' is the number of elements in the input array. There are two nested loops, each iterating over the entire array. Therefore, for each element in the outer loop, the inner loop compares with every other element in the array. The worst-case scenario occurs when every pair of strings in the array is compared, resulting in a quadratic time complexity of O(n^2).
Space Complexity:
The space complexity of the hasPrefix method is O(1), constant space. The method uses a fixed amount of additional memory, regardless of the size of the input array. The only variables used are integers (i and j) used for iteration and the input array itself (arr). The method does not rely on any additional data structures whose size scales with the input.
Approach 2: Using sorting binary search
ALGORITHM:
Step 1: Use Arrays·sort(arr) to lexicographically sort the input array of strings arr· This ensures that strings with common prefixes are grouped together·
Step 2: Use a for loop to iterate through each element of the array (arr)·
Step 3: The loop starts from the first element and goes up to the second-to-last element (for (int i = 0; i < arr·length - 1; i++))·
Step 4: For each element at index i, perform a binary search (binarySearch method) on the remaining portion of the array (from index i + 1 to the end) to check if any subsequent string is a prefix of the current string·
Step 5: Implement the binarySearch method to check if a given target string (arr[i]) is a prefix of any element in the sorted array·
Step 6: Use a while loop to perform binary search within the specified range (low to high indices)·
Step 7: Within the binary search loop, compare the target string (arr[i]) with the middle element (arr[mid]) using arr[mid]·startsWith(target) to check if it is a prefix·
Step 8: Depending on the result of the comparison, adjust the low and high pointers in the binary search·
Step 9: If the middle element is greater than the target string, set high to mid - 1· If it is less, set low to mid + 1·
Step 10: If a matching prefix is found during the binary search, return true·
Step 11: If the entire array has been searched, and no matching prefix is found, return false after the outer loop completes·
Step 12: In the main method, create examples (e·g·, arrays of strings) and call the hasPrefix method on each example, printing "Yes" if there is a matching prefix, and "No" otherwise·
Step 13: Run the program and observe the output for each example, confirming whether a string is a prefix of another in the given arrays·
Implementation:
The implementation of the above steps given below
FileName: StringPrefixChecker.java
import java.util.Arrays;
public class StringPrefixChecker {
// Sorting and Binary Search approach to check if a string is a prefix of an array
public static boolean hasPrefix(String[] arr) {
// Sort the array in lexicographical order
Arrays.sort(arr);
// Iterate through each element and check if it is a prefix using binary search
for (int i = 0; i < arr.length - 1; i++) {
if (binarySearch(arr, arr[i], i + 1, arr.length - 1)) {
return true;
}
}
return false;
}
// Binary search method to check if a string is a prefix of any element in a sorted array
private static boolean binarySearch(String[] arr, String target, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid].startsWith(target)) {
return true;
} else if (arr[mid].compareTo(target) > 0) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
public static void main(String[] args) {
// Example 1:
String[] arr1 = {"baj", "mnc", "rahi", "banjo"};
System.out.println("Example 1: " + (hasPrefix(arr1) ? "Yes" : "No"));
// Example 2:
String[] arr2 = {"bahe", "baj", "jabf", "bahej"};
System.out.println("Example 2: " + (hasPrefix(arr2) ? "Yes" : "No"));
// Example 3:
String[] arr3 = {"book", "bookmark", "boot", "booty"};
System.out.println("Example 3: " + (hasPrefix(arr3) ? "Yes" : "No"));
// Example 4:
String[] arr4 = {"green", "greenery", "greenhouse", "greed"};
System.out.println("Example 4: " + (hasPrefix(arr4) ? "Yes" : "No"));
}
}
Output:
Example 1: No
Example 2: Yes
Example 3: Yes
Example 4: Yes
Complexity Analysis:
Time Complexity:
The time complexity of the algorithm is O(n log n), where 'n' is the number of elements in the input array· The most significant factor contributing to the time complexity is the sorting operation, which has a time complexity of O(n log n) in the worst case for Java's Arrays·sort method· After sorting, the binary search is performed for each element in the array· Binary search has a time complexity of O(log n)· Therefore, the dominant factor is the sorting, and the overall time complexity is O(n log n)·
Space Complexity:
The space complexity of the algorithm is O(1), constant space· The algorithm uses a constant amount of additional space, regardless of the size of the input array· Sorting is performed in-place, and the binary search utilizes only a few variables (low, high, mid) without requiring additional data structures· Hence, the space complexity remains constant at O(1)·
Approach 3: Using Regex method
ALGORITHM:
Step 1: Use a loop to iterate through each element in the array·
Step 2: For each element, create a regex pattern that starts with ^ (indicating the beginning) and includes the quoted string (treating special characters as literals) from the array· Append ·* to allow for any characters that may follow·
Step 3: Use a nested loop to iterate through subsequent elements in the array, starting from the next position after the current element·
Step 4: For each pair of elements, apply the regex pattern to the current and subsequent elements·
Step 5: If a match is found (i·e·, the subsequent element starts with the current element), return true·
Step 6: If no matching prefix is found during the nested loop, return false·
Step 7: In the main method, create examples (arrays of strings) and call the hasPrefix method on each example·
Step 8: Print "Yes" if a string is a prefix of another in the given arrays, and "No" otherwise·
Step 9: Execute the program and observe the output for each example, confirming whether a string is a prefix of another in the array·
Implementation:
The implementation of the above steps given below
FileName: StringPrefixChecker.java
import java.util.regex.Pattern;
public class StringPrefixChecker {
// Regex Matching approach to check if a string is a prefix of an array
public static boolean hasPrefix(String[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// Create a regex pattern to match the prefix of arr[i]
String regex = "^" + Pattern.quote(arr[i]) + ".*";
// Iterate through subsequent elements and check for a match using regex
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].matches(regex)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
// Example 1:
String[] arr1 = {"baj", "mnc", "rahi", "banjo"};
System.out.println("Example 1: " + (hasPrefix(arr1) ? "Yes" : "No"));
// Example 2:
String[] arr2 = {"bahe", "baj", "jabf", "bahej"};
System.out.println("Example 2: " + (hasPrefix(arr2) ? "Yes" : "No"));
// Example 3:
String[] arr3 = {"book", "bookmark", "boot", "booty"};
System.out.println("Example 3: " + (hasPrefix(arr3) ? "Yes" : "No"));
// Example 4:
String[] arr4 = {"green", "greenery", "greenhouse", "greed"};
System.out.println("Example 4: " + (hasPrefix(arr4) ? "Yes" : "No"));
}
}
Output:
Example 1: No
Example 2: Yes
Example 3: Yes
Example 4: Yes
Complexity Analysis:
Time Complexity:
The time complexity of the algorithm is O(n^2), where 'n' is the number of elements in the input array·There is an outer loop that iterates through each element in the array, and for each element, there is a nested loop that iterates through subsequent elements· In the worst-case scenario, each element needs to be compared with every other element, resulting in a quadratic time complexity of O(n^2)·
Space Complexity:
The space complexity of the algorithm is O(1), constant space· The algorithm uses a constant amount of additional space regardless of the size of the input array· The primary space usage comes from the variables used in the loops, the regex pattern, and the temporary storage during method execution· The space required for these variables does not scale with the size of the input·
Approach 4: Prefix Sum Array
ALGORITHM:
Step 1: Create an array called prefixSum to store the count of strings that have a given string as a prefix.
Step 2: Initialize each element in the prefixSum array to 0.
Step 3: Use two nested loops to iterate through each pair of strings in the array.
Step 4: For each pair (i, j), check if the string at index j starts with the string at index i.
Step 5: If true, increment the corresponding element in the prefixSum array at index i.
Step 6: Use break to exit the inner loop since we only need to count the prefix once for each string.
Step 7: After calculating the prefix sum, iterate through the prefixSum array.
Step 8: If any element in the prefixSum array is greater than 0, return true as it indicates the presence of a prefix.
Step 9: If no element in the prefixSum array is greater than 0, return false.
Implementation:
The implementation of the above steps given below.
FileName: StringPrefixChecker.java
import java.util.*;
public class StringPrefixChecker {
// Prefix Sum Array approach to check if a string is a prefix of an array
public static boolean hasPrefix(String[] arr) {
// Calculate the prefix sum array
int[] prefixSum = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].startsWith(arr[i])) {
prefixSum[i]++;
break; // No need to continue checking subsequent elements
}
}
}
// Check if any element in the prefix sum array is greater than 0
for (int count : prefixSum) {
if (count > 0) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// Example 1:
String[] arr1 = {"baj", "mnc", "rahi", "banjo"};
System.out.println("Example 1: " + (hasPrefix(arr1) ? "Yes" : "No"));
// Example 2:
String[] arr2 = {"bahe", "baj", "jabf", "bahej"};
System.out.println("Example 2: " + (hasPrefix(arr2) ? "Yes" : "No"));
// Example 3:
String[] arr3 = {"book", "bookmark", "boot", "booty"};
System.out.println("Example 3: " + (hasPrefix(arr3) ? "Yes" : "No"));
// Example 4:
String[] arr4 = {"green", "greenery", "greenhouse", "greed"};
System.out.println("Example 4: " + (hasPrefix(arr4) ? "Yes" : "No"));
}
}
Output:
Example 1: No
Example 2: Yes
Example 3: Yes
Example 4: Yes
Complexity Analysis:
Time Complexity:
The time complexity of the algorithm is O(n^2), where 'n' is the number of elements in the input array. There are two nested loops, each iterating through the entire array. For each pair of strings, there is a check for a prefix match using startsWith. In the worst-case scenario, each element needs to be compared with every other element, resulting in a quadratic time complexity of O(n^2).
Space Complexity:
The space complexity of the algorithm is O(n), where 'n' is the number of elements in the input array. The space complexity is dominated by the prefixSum array, which has 'n' elements, each representing the count of strings with a given string as a prefix. In the worst case, every element in the array contributes to the prefixSum array, leading to a linear space complexity of O(n).