Print all valid words from given dictionary that are possible using Characters of given Array

0 0 4 minutes read

Given a dictionary of strings dict[] and a character array arr[]. Print all valid words of the dictionary that are possible using characters from the given character array.
Examples:

Input: dict – [“go”, “bat”, “me”, “eat”, “goal”, boy”, “run”]
arr[] = [‘e’, ‘o’, ‘b’, ‘a’, ‘m’, ‘g’, ‘l’]Output: “go”, “me”, “goal”.
Explanation: Only all the characters of these three strings are present in the dictionary.

Input: Dict= [“goa”, “bait”, “mess”, “ate”, “goal”, “girl”, “rain”]arr[]= [‘s’, ‘o’, ‘t’, ‘a’, ‘e’, ‘g’, ‘l’, ‘i’, ‘r’]Output: “goa”, “ate”, “goal”, “girl”

Approach: The problem can be solved by checking the characters of each string of the dictionary. If all the characters of a string is present then that string can be formed. Follow the steps mentioned below to solve the problem.

Concatenate all the characters and make a string.
Traverse each word in a string and find whether all the characters of each word are present in concatenated string or not.

Follow the illustration shown below for better understanding.

Illustration: Consider the example below.

dict[] = [“go”, “bat”, “eat”, “meat”, “goal”, “boy”, “run”],
arr[] = [‘e’, ‘o’, ‘b’, ‘a’, ‘m’, ‘g’, ‘l’]

concatenated string= e o b a m g l

now if we traverse “go”

indexOf(“g”) in “eobamgl” is 5

indexOf(“o”) in “eobamgl” is 1

This means all the indexes are present. Hence we will print “go”

If any of the indexes are not present, that will not be included.

Similarly “me” and “goal” also satisfies the condition.

So the output is “go”, “goal” and “me”.

Below is the implementation of the above approach.

C++

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the words
void printWord(string str, string s) {
    for (int i = 0; i < str.size(); i++) {
        if (s.find(str[i]) == string::npos) {
            return;
        }
    }
    cout << str << endl;
}
 
// Function to find the words
void findWord(vector<string> str1, vector<char> str2) {
    string s = "";
    for (int i = 0; i < str2.size(); i++) {
        s += str2[i];
    }
    for (int i = 0; i < str1.size(); i++) {
        printWord(str1[i], s);
    }
}
 
int main() {
    vector<string> str1 = {"go", "bat", "me", "eat",
                "goal", "boy", "run"};
    vector<char> str2 = {'e', 'o', 'b', 'a', 'm', 'g', 'l'};
    findWord(str1, str2);
    return 0;
}
 
// This code is contributed by Samim Hossain Mondal.

Java

// Java code to implement the above approach
public class GFG{
 
  // Function to print the words
  public static void printWord(String str, String s) {
    for (int i = 0; i < str.length(); i++) {
      if (s.indexOf(str.charAt(i)) < 0) {
        return;
      }
    }
    System.out.println(str);
  }
 
  // Function to find the words
  public static void findWord(String[] str1, char[] str2) {
    String s = "";
    for (int i = 0; i < str2.length; i++) {
      s += str2[i];
    }
    for (int i = 0; i < str1.length; i++) {
      printWord(str1[i], s);
    }
  }
 
  public static void main(String args[]) {
    String[] str1 = {"go", "bat", "me", "eat", "goal", "boy", "run"};
    char[] str2 = {'e', 'o', 'b', 'a', 'm', 'g', 'l'};
    findWord(str1, str2);
  }
}
 
// This code is contributed by Saurabh Jaiswal

Python3

# python code to implement the above approach
 
# Function to print the words
def printWord(str, s):
    for i in range(0, len(str)):
        if (not (str[i] in s)):
            return
 
    print(str)
 
# Function to find the words
def findWord(str1, str2):
    s = ""
    for i in str2:
        s += i
 
    for i in range(0, len(str1)):
        printWord(str1[i], s)
 
# Driver Code
if __name__ == "__main__":
    str1 = ["go", "bat", "me", "eat", "goal", "boy", "run"]
 
    str2 = ["e", "o", "b", "a", "m", "g", "l"]
 
    findWord(str1, str2)
 
    # This code is contributed by rakeshsahni

C#

// C# code to implement the above approach
using System;
 
class GFG {
 
  // Function to print the words
  public static void printWord(string str, string s)
  {
    for (int i = 0; i < str.Length; i++) {
      if (s.IndexOf((str[i])) < 0) {
        return;
      }
    }
    Console.WriteLine(str);
  }
 
  // Function to find the words
  public static void findWord(string[] str1, char[] str2)
  {
    string s = "";
    for (int i = 0; i < str2.Length; i++) {
      s += str2[i];
    }
    for (int i = 0; i < str1.Length; i++) {
      printWord(str1[i], s);
    }
  }
 
  public static void Main(string[] args)
  {
    string[] str1 = { "go",   "bat", "me", "eat",
                     "goal", "boy", "run" };
    char[] str2 = { 'e', 'o', 'b', 'a', 'm', 'g', 'l' };
    findWord(str1, str2);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
    // JavaScript code to implement the above approach
 
    // Function to print the words
    function printWord(str, s) {
        for (var i = 0; i < str.length; i++) {
            if (s.indexOf(str[i]) < 0) {
                return;
            }
        }
        document.write(str);
        document.write("<br>");
    }
     
    // Function to find the words
    function findWord(str1, str2) {
        var s = "";
        for (var i in str2) {
            s += str2[i];
        }
        for (var i = 0; i < str1.length; i++) {
            printWord(str1[i], s);
        }
    }
     
    var str1 = ["go", "bat", "me", "eat",
                "goal", "boy", "run"];
    var str2 = ["e", "o", "b", "a", "m", "g", "l"];
    findWord(str1, str2);
</script>

Output

go
me
goal

Time Complexity: O(N * K) where N is the length of the dict[] and k is the length of arr[].
Auxiliary Space: O(1)

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!