Given an array of strings, the task is to print “Yes” if it contains a string that is a prefix of another string otherwise, print “No”.
Examples:
Input: arr[] = {“rud”, “rudra”, “rahi”}
Output: Yes
Explanation: arr[0] = “rud” is a prefix of arr[1] = “rudra”, that’s why “Yes” is the output.Input: arr[] = {“baj”, “mnc”, “rahi”, “banjo”}
Output: NoInput: arr[] = {“bahe”, “baj”, “jabf”, “bahej”}
Output: Yes
Approach: To solve the problem follow the below idea:
The approach basically requires us to match one string to another, such that checking whether one contains prefix of another, with the help of find method which returns the first position where there is a prefix match, and in case of prefix it would definitely be zero.
Steps to follow to implement the approach:
- The “hasPrefix” function takes an array of strings “arr” and its size “n” as input.
- It then iterates through each string in the array, and for each string, it checks if it is a prefix of any other string in the array using the “find” method of the “string” class. If it is, the function immediately returns “true”.
- If no string is found to be a prefix of another string, the function returns “false”.
- The main function creates an example string array, calls the “hasPrefix” function, and prints “Yes” if the function returns “true”, and “No” otherwise.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <iostream>#include <string>using namespace std;bool hasPrefix(string arr[], int n){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Matching ith and jth strings // whether one is prefix // of another if (i != j && arr[j].find(arr[i]) == 0) { return true; } } } return false;}// Driver's codeint main(){ string arr[] = { "rud", "rudra", "rahi" }; int n = sizeof(arr) / sizeof(arr[0]); if (hasPrefix(arr, n)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
// Java code for the sameimport java.util.Arrays;public class Main { public static boolean hasPrefix(String[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { // Matching ith and jth strings whether one is // prefix of another if (i != j && arr[j].indexOf(arr[i]) == 0) { return true; } } } return false; } // Driver's code public static void main(String[] args) { String[] arr = { "rud", "rudra", "rahi" }; if (hasPrefix(arr)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
C#
// C# code for the above implementationusing System;public class MainClass { public static bool HasPrefix(string[] arr) { for (int i = 0; i < arr.Length; i++) { for (int j = 0; j < arr.Length; j++) { // Matching ith and jth strings whether one is // prefix of another if (i != j && arr[j].IndexOf(arr[i]) == 0) { return true; } } } return false; } // Driver's code public static void Main() { string[] arr = { "rud", "rudra", "rahi" }; if (HasPrefix(arr)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
// Function to check if any string in the array is a prefix of another stringfunction hasPrefix(arr) {for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length; j++) { // Matching ith and jth strings // whether one is prefix // of anotherif (i !== j && arr[j].startsWith(arr[i])) {return true; // Return true if a prefix is found}}}return false; // Return false if no prefix is found}// Driver's codeconst arr = ["rud", "rudra", "rahi"];if (hasPrefix(arr)) {console.log("Yes"); // Output "Yes" if a prefix is found} else {console.log("No"); // Output "No" if no prefix is found}//This code is contributed by rudra1807raj |
Python3
# Function to check if any string in the array is a prefix of another stringdef has_prefix(arr): for i in range(len(arr)): for j in range(len(arr)): # Check if the i-th and j-th strings are different and # if the j-th string starts with the i-th string if i != j and arr[j].startswith(arr[i]): return True # Return True if a prefix is found return False # Return False if no prefix is found# Driver's codearr = ["rud", "rudra", "rahi"]if has_prefix(arr): print("Yes") # Output "Yes" if a prefix is foundelse: print("No") # Output "No" if no prefix is found #This code is contributed by rudra1807raj |
Yes
Time Complexity: O(n^2 * m), where n is the length of the input array and m is the maximum length of a string in the array. This is because the code uses nested loops to compare every pair of strings in the array, and for each pair, it uses the find method to check if one string is a prefix of the other. The find method has a time complexity of O(m).
Auxiliary Space: O(1), as it only uses a fixed amount of memory to store the input array and a few loop variables. The space used does not depend on the size of the input.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
