Given a pattern ‘pattern‘ and a sentence ‘s‘, the task is to check if the words in the given sentence occur based on the pattern represented in the ‘pattern‘.
Examples:
Input: pattern = “abba”, s = “neveropen for for neveropen”
Output: true
Explanation: In the pattern, ‘a’ denotes ‘neveropen’ and ‘b’ denotes ‘for’. Therefore, sentence ‘s’ follows the pattern ‘pattern’Input: pattern = “abc”, s = “neveropen for neveropen”
Output: false
Approach:
The given problem can be solved by generalizing the pattern formed by words in a given sentence and the characters in the given pattern. Then just check if both the generalized pattern and the given pattern are the same or not. Follow the below steps to solve the problem:
- Create a map to store each word and assign a value to each unique word based on its occurrence.
- Example: for the sentence “neveropen for neveropen”, the map will be [{“neveropen”, 0}, {“for”, 1}]
- Similarly, map the occurrence of each character in the pattern
- Then match the pattern index by index in both maps and print the result
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the words in given// sentence follows the given patternbool wordPattern(string pattern, string s){ // Stores the occurrence of each word // of a sentence map<string, int> mp; int ch = -1; string temp = ""; string str = "", p = ""; for (int i = 0; i < s.length(); i++) { if (s[i] == ' ') { if (!temp.empty() && mp.find(temp) == mp.end()) { mp.insert({ temp, ++ch }); } if (mp.find(temp) != mp.end()) str += ((char)((mp.find(temp))->second + 'a')); temp = ""; } else temp += s[i]; } if (!temp.empty() && mp.find(temp) == mp.end()) mp.insert({ temp, ++ch }); if (mp.find(temp) != mp.end()) str += ((char)((mp.find(temp))->second + 'a')); map<char, int> m; ch = -1; for (int i = 0; i < pattern.length(); i++) { if (m.find(pattern[i]) == m.end()) m.insert({ pattern[i], ++ch }); if (m.find(pattern[i]) != m.end()) p += ((char)((m.find(pattern[i]))->second + 'a')); } return p == str;}// Driver Codeint main(){ string pattern = "abba", s = "neveropen for for neveropen"; cout << (wordPattern(pattern, s) ? "true" : "false"); return 0;} |
Java
import java.util.HashMap;public class Main { // Function to check if the words in given // sentence follows the given pattern static boolean wordPattern(String pattern, String s) { // Stores the occurrence of each word of a sentence HashMap<String, Integer> mp = new HashMap<>(); int ch = -1; String temp = ""; String str = "", p = ""; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') { if (!temp.isEmpty() && !mp.containsKey(temp)) { mp.put(temp, ++ch); } if (mp.containsKey(temp)) { str += (char) (mp.get(temp) + 'a'); } temp = ""; } else { temp += s.charAt(i); } } if (!temp.isEmpty() && !mp.containsKey(temp)) { mp.put(temp, ++ch); } if (mp.containsKey(temp)) { str += (char) (mp.get(temp) + 'a'); } HashMap<Character, Integer> m = new HashMap<>(); ch = -1; for (int i = 0; i < pattern.length(); i++) { if (!m.containsKey(pattern.charAt(i))) { m.put(pattern.charAt(i), ++ch); } if (m.containsKey(pattern.charAt(i))) { p += (char) (m.get(pattern.charAt(i)) + 'a'); } } return p.equals(str); } // Driver Code public static void main(String[] args) { String pattern = "abba"; String s = "neveropen for for neveropen"; System.out.println(wordPattern(pattern, s) ? "true" : "false"); }} |
Python3
# Python program for the above approach# Function to check if the words in given# sentence follows the given patterndef wordPattern(pattern, s): # Stores the occurrence of each word # of a sentence mp = {} ch = -1 temp = "" st = "" p = "" for i in range(0, len(s)): if (s[i] == ' '): if ((len(temp)) and (not mp.__contains__(temp))): ch += 1 mp[temp] = ch if (mp.__contains__(temp)): st += ((chr)((mp[temp]) + 97)) temp = "" else: temp += s[i] if ((len(temp)) and (not mp.__contains__(temp))): ch += 1 mp[temp] = ch if (mp.__contains__(temp)): st += ((chr)((mp[temp]) + 97)) m = {} ch = -1 for i in range(0, len(pattern)): if (not m.__contains__(pattern[i])): ch += 1 m[pattern[i]] = ch if (m.__contains__(pattern[i])): p += ((chr)(m[pattern[i]] + 97)) return p == st# Driver Codepattern = "abba"s = "neveropen for for neveropen"ans = wordPattern(pattern, s)print("true" if ans else "false")# This code is contributed by ninja_hattori. |
C#
using System;using System.Collections.Generic;class Program{ // Function to check if the words in given // sentence follows the given pattern static bool WordPattern(string pattern, string s) { // Stores the occurrence of each word // of a sentence Dictionary<string, int> mp = new Dictionary<string, int>(); int ch = -1; string temp = ""; string str = "", p = ""; // Loop through the characters in the input string for (int i = 0; i < s.Length; i++) { if (s[i] == ' ') { if (!string.IsNullOrEmpty(temp) && !mp.ContainsKey(temp)) { mp[temp] = ++ch; } if (mp.ContainsKey(temp)) { str += (char)(mp[temp] + 'a'); } temp = ""; } else { temp += s[i]; } } if (!string.IsNullOrEmpty(temp) && !mp.ContainsKey(temp)) { mp[temp] = ++ch; } if (mp.ContainsKey(temp)) { str += (char)(mp[temp] + 'a'); } Dictionary<char, int> m = new Dictionary<char, int>(); ch = -1; // Loop through the characters in the pattern for (int i = 0; i < pattern.Length; i++) { if (!m.ContainsKey(pattern[i])) { m[pattern[i]] = ++ch; } if (m.ContainsKey(pattern[i])) { p += (char)(m[pattern[i]] + 'a'); } } return p == str; } // Driver Code static void Main() { string pattern = "abba"; string s = "neveropen for for neveropen"; Console.WriteLine(WordPattern(pattern, s) ? "true" : "false"); }} |
Javascript
// Function to check if the words in the given sentence follow the given patternfunction wordPattern(pattern, s) { // Stores the occurrence of each word in a sentence const wordToPattern = new Map(); let patternIndex = 0; let temp = ""; let patternStr = ""; let wordToPatternIndex = -1; for (let i = 0; i < s.length; i++) { if (s[i] === ' ') { if (temp.length && !wordToPattern.has(temp)) { wordToPatternIndex++; wordToPattern.set(temp, wordToPatternIndex); } if (wordToPattern.has(temp)) { patternStr += String.fromCharCode(97 + wordToPattern.get(temp)); } temp = ""; } else { temp += s[i]; } } if (temp.length && !wordToPattern.has(temp)) { wordToPatternIndex++; wordToPattern.set(temp, wordToPatternIndex); } if (wordToPattern.has(temp)) { patternStr += String.fromCharCode(97 + wordToPattern.get(temp)); } const patternToIndex = new Map(); patternIndex = -1; let patternStrFinal = ""; for (let i = 0; i < pattern.length; i++) { if (!patternToIndex.has(pattern[i])) { patternIndex++; patternToIndex.set(pattern[i], patternIndex); } if (patternToIndex.has(pattern[i])) { patternStrFinal += String.fromCharCode(97 + patternToIndex.get(pattern[i])); } } return patternStrFinal === patternStr;}// Driver Codeconst pattern = "abba";const s = "neveropen for for neveropen";const ans = wordPattern(pattern, s);console.log(ans ? "true" : "false"); |
Output
true
Time Complexity: O(NlogN), as we are inserting elements into map and finding values from the map inside the loop.
Auxiliary Space: O(N), as we are using extra space for map.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
