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 wordsvoid 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 wordsvoid 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 approachpublic 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 wordsdef printWord(str, s): for i in range(0, len(str)): if (not (str[i] in s)): return print(str)# Function to find the wordsdef findWord(str1, str2): s = "" for i in str2: s += i for i in range(0, len(str1)): printWord(str1[i], s)# Driver Codeif __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 approachusing 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> |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
