Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Word Pattern

Easy · Hashing & Two Pointers · Asked at Amazon, Uber, Dropbox, Zoho

Does the sentence follow the pattern? Each letter of pattern must map to exactly one word, and each word to exactly one letter (a one-to-one match), in order. Print YES or NO.

Input

First line: pattern (lowercase letters). Second line: words separated by single spaces.

Output

YES or NO.

Constraints

Use two maps (letter → word and word → letter). Different lengths mean NO immediately.

Example 1

Input

abba
dog cat cat dog

Output

YES

Example 2

Input

abba
dog dog dog dog

Output

NO

Hints

  1. If the number of words differs from the pattern length, the answer is NO.
  2. One map is not enough: "abba" vs "dog dog dog dog" passes a letter→word check. Also check word→letter.

Approach

Split the second line into words. Walk both sequences together, maintaining letter → word and word → letter maps. If either map already has an entry that disagrees with the current pair, it is not a bijection — print NO. Otherwise record the pair. Surviving the whole walk means YES.

Complexity: O(total length) time · O(k) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string pat, line, w;
    getline(cin, pat);
    getline(cin, line);
    stringstream ss(line);
    vector<string> words;
    while (ss >> w) words.push_back(w);
    while (!pat.empty() && isspace((unsigned char)pat.back())) pat.pop_back();
    if (words.size() != pat.size()) {
        cout << "NO\n";
        return 0;
    }
    map<char, string> a;
    map<string, char> b;
    for (size_t i = 0; i < pat.size(); i++) {
        if ((a.count(pat[i]) && a[pat[i]] != words[i]) || (b.count(words[i]) && b[words[i]] != pat[i])) {
            cout << "NO\n";
            return 0;
        }
        a[pat[i]] = words[i];
        b[words[i]] = pat[i];
    }
    cout << "YES\n";
    return 0;
}

Python solution

import sys

lines = sys.stdin.read().split("\n")
pat, words = lines[0].strip(), lines[1].split()
ok = len(pat) == len(words)
a, b = {}, {}
for c, w in zip(pat, words):
    if a.get(c, w) != w or b.get(w, c) != c:
        ok = False
        break
    a[c], b[w] = w, c
print("YES" if ok else "NO")

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String pat = br.readLine().trim();
        String[] words = br.readLine().trim().split("\\s+");
        if (words.length != pat.length()) {
            System.out.println("NO");
            return;
        }
        Map<Character, String> a = new HashMap<>();
        Map<String, Character> b = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            char c = pat.charAt(i);
            if ((a.containsKey(c) && !a.get(c).equals(words[i])) || (b.containsKey(words[i]) && b.get(words[i]) != c)) {
                System.out.println("NO");
                return;
            }
            a.put(c, words[i]);
            b.put(words[i], c);
        }
        System.out.println("YES");
    }
}

Solve Word Pattern online · All practice problems