Check if given String is prefix subarray of the given Array

0 0 4 minutes read

Given a string str and an array of words word[], the task is to find whether str is a prefix string of word[].

Examples:

Input: str = “indiaismycountry”,
word[] = {“india”, “is”, “my”, “country”, “and”, “i”, “love”, “india”}
Output: true
Explanation: String str can be made by concatenating “india”, “is”, “my” and “country” together.

Input: str = “indianism”,
word[] = {“india”, “is”, “my”, “country”, “and”, “i”, “love”, “india”}
Output: false
Explanation: It is impossible to make str using the prefixes of the word array.

Approach: This is a simple implementation related problem. Follow the steps mentioned below:

Take an empty string named ans.
Iterate over the word array and keep on adding each element of the word array to ans.
After adding to ans comparing it with the s, if they both match simply return true else continue.
If the iteration ends and ans doesn’t matches with the s then return false.

Below is the C++ program to implement the above approach-

C++

// C++ program to implement the
// given approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether string
// is prefix
bool isPrefixString(string s,
                    vector<string>& word)
{
    // ans is taken as an empty string
    string ans = "";
 
    // N is used to store
    // the size of word array
    int N = word.size();
 
    // Iterating over the word array
    for (int i = 0; i < N; i++) {
        // Adding element by element
        // of the array
        ans += word[i];
 
        // If ans and str are same
        // return true
        if (ans == s)
            return true;
    }
 
    // As iteration is ending which means
    // string is not prefix so return false.
    return false;
}
 
// Driver code
int main()
{
    string str = "indiaismycountry";
    vector<string> word
        = { "india", "is", "my",
            "country", "and", "i",
            "love", "india" };
    bool ans = isPrefixString(str, word);
    if (ans)
        cout << "True";
    else
        cout << "False";
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to check whether string
  // is prefix
  static Boolean isPrefixString(String s,
                                String word[])
  {
     
    // ans is taken as an empty string
    String ans = "";
 
    // N is used to store
    // the size of word array
    int N = word.length;
 
    // Iterating over the word array
    for (int i = 0; i < N; i++) {
      // Adding element by element
      // of the array
      ans += word[i];
      // If ans and str are same
      // return true
      if (ans.equals(s))
        return true;
    }
 
    // As iteration is ending which means
    // string is not prefix so return false.
    return false;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    String str = "indiaismycountry";
    String word[]
      = { "india", "is", "my",
         "country", "and", "i",
         "love", "india" };
    Boolean ans = isPrefixString(str, word);
    if (ans)
      System.out.println("True");
    else
      System.out.println("False");
  }
}
 
// This code is contributed by hrithikgarg03188.

Python

# Pyhton program to implement the
# given approach
 
# Function to check whether string
# is prefix
def isPrefixString(s, word):
 
    # ans is taken as an empty string
    ans = ""
 
    # N is used to store
    # the size of word array
    N = len(word)
 
    # Iterating over the word array
    for i in range(0, N):
 
        # Adding element by element
        # of the array
        ans = ans + (word[i])
 
        # If ans and str are same
        # return true
        if (ans == s):
            return True
 
    # As iteration is ending which means
    # string is not prefix so return false.
    return False
 
# Driver code
str = "indiaismycountry"
word = ["india", "is", "my", "country", "and", "i", "love", "india"]
 
ans = isPrefixString(str, word)
if (ans == True):
    print("True")
else:
    print("False")
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# program for the above approach
using System;
class GFG {
 
  // Function to check whether string
  // is prefix
  static bool isPrefixString(string s,
                             string []word)
  {
 
    // ans is taken as an empty string
    string ans = "";
 
    // N is used to store
    // the size of word array
    int N = word.Length;
 
    // Iterating over the word array
    for (int i = 0; i < N; i++) 
    {
 
      // Adding element by element
      // of the array
      ans += word[i];
 
      // If ans and str are same
      // return true
      if (ans.Equals(s))
        return true;
    }
 
    // As iteration is ending which means
    // string is not prefix so return false.
    return false;
  }
 
  // Driver code
  public static void Main ()
  {
    string str = "indiaismycountry";
    string []word
      = { "india", "is", "my",
         "country", "and", "i",
         "love", "india" };
    bool ans = isPrefixString(str, word);
    if (ans)
      Console.WriteLine("True");
    else
      Console.WriteLine("False");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
      // JavaScript code for the above approach 
 
      // Function to check whether string
      // is prefix
      function isPrefixString(s, word)
      {
       
          // ans is taken as an empty string
          let ans = "";
 
          // N is used to store
          // the size of word array
          let N = word.length;
 
          // Iterating over the word array
          for (let i = 0; i < N; i++)
          {
           
              // Adding element by element
              // of the array
              ans += word[i];
 
              // If ans and str are same
              // return true
              if (ans == s)
                  return true;
          }
 
          // As iteration is ending which means
          // string is not prefix so return false.
          return false;
      }
 
      // Driver code
      let str = "indiaismycountry";
      let word
          = ["india", "is", "my",
              "country", "and", "i",
              "love", "india"];
      let ans = isPrefixString(str, word);
      if (ans)
          document.write("True");
      else
          document.write("False");
 
     // This code is contributed by Potta Lokesh
  </script>

Output

True

Time Complexity: O(N), N is the size of the word array.
Space Complexity: O(M) where M is the length of str

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!