Check if a two character string can be made using given words
Given a string of two characters and n distinct words of two characters. The task is to find if it is possible to arrange given words in such a way that the concatenated string has the given two character string as a substring. We can append a word multiple times.
Examples:
Input : str = "ya" words[] = {"ah", "oy", "to", "ha"} Output : YES We can join "oy" and then "ah", and then "ha" to form the string "oyahha" which contains the string "ya". So, the answer is "YES" Input : str[] = "ha" words[] = "ah" Output :YES The string "ahah" contains "ha" as a substring. Input : str = "hp" words[] = {"ht", "tp"| Output :NO We can't produce a string containing "hp" as a sub-string. Note that we can join "ht" and then "tp" producing "http", but it doesn't contain the "hp" as a sub-string.
If we look at the given examples carefully, we can see that our answer will be “YES” if any of the following conditions is true,
- str is equal to any one of the N words
- str is equal to reverse of any of the words.
- It first letter of str is equal to last letter of any of the given N strings and last letter is equal to the first letter of any of the given N strings.
Otherwise our output will always be NO.
Below is the implementation of the above approach.
C++
Java
Python3
C#
PHP
Javascript
Output
Yes
Time Complexity: O(n), where n represents the size of the given vector.
Auxiliary Space: O(1), no extra space is required, so it is a constant.