Uncategorized

Check if Prefix String exists in the Array

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: No

Input: 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++

#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++) {

  

            

            

            

            if (i != j && arr[j].find(arr[i]) == 0) {

                return true;

            }

        }

    }

    return false;

}

  

int 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

import 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++) {

                

                

                if (i != j && arr[j].indexOf(arr[i]) == 0) {

                    return true;

                }

            }

        }

        return false;

    }

  

    

    public static void main(String[] args)

    {

        String[] arr = { "rud", "rudra", "rahi" };

  

        if (hasPrefix(arr)) {

            System.out.println("Yes");

        }

        else {

            System.out.println("No");

        }

    }

}

C#

using 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++) {

                

                

                if (i != j && arr[j].IndexOf(arr[i]) == 0) {

                    return true;

                }

            }

        }

        return false;

    }

  

    

    public static void Main()

    {

        string[] arr = { "rud", "rudra", "rahi" };

  

        if (HasPrefix(arr)) {

            Console.WriteLine("Yes");

        }

        else {

            Console.WriteLine("No");

        }

    }

}

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.

By Julio MarchiPosted on