Check if words in given sentence occur based on the given pattern ❤️

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 = “Beginner for for Beginner”
Output: true
Explanation: In the pattern, ‘a’ denotes ‘Beginner’ and ‘b’ denotes ‘for’. Therefore, sentence ‘s’ follows the pattern ‘pattern’

Input: pattern = “abc”, s = “Beginner for Beginner”
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 “Beginner for Beginner”, the map will be [{“Beginner”, 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 pattern
bool 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 Code
int main()
{
 
    string pattern = "abba",
           s = "Beginner for for Beginner";
    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 = "Beginner for for Beginner";
        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 pattern
def 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 Code
pattern = "abba"
s = "Beginner for for Beginner"
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 = "Beginner for for Beginner";
        Console.WriteLine(WordPattern(pattern, s) ? "true" : "false");
    }
}

Javascript

// Function to check if the words in the given sentence follow the given pattern
function 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 Code
const pattern = "abba";
const s = "Beginner for for Beginner";
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.

Check if words in given sentence occur based on the given pattern

C++

Java

Python3

C#

Javascript

Contact Us