notes/OJ notes/pages/Leetcode Word-Pattern.md

# Leetcode Word-Pattern

2022-09-05 19:27

> ##### Data structures:
>
> #DS #string
>
> ##### Difficulty:
>
> #coding_problem #difficulty_easy
>
> ##### Additional tags:
>
> #leetcode
>
> ##### Revisions:
>
> N/A

##### Links:

- [Link to problem]()

---

### Problem

Given a `pattern` and a string `s`, find if `s` follows the same pattern.

Here **follow** means a full match, such that there is a bijection between a letter in `pattern` and a **non-empty** word in `s`.

#### Examples

**Example 1:**

**Input:** pattern = "abba", s = "dog cat cat dog"
**Output:** true

**Example 2:**

**Input:** pattern = "abba", s = "dog cat cat fish"
**Output:** false

**Example 3:**

**Input:** pattern = "aaaa", s = "dog cat cat dog"
**Output:** false

#### Constraints

- `1 <= pattern.length <= 300`
- `pattern` contains only lower-case English letters.
- `1 <= s.length <= 3000`
- `s` contains only lowercase English letters and spaces `' '`.
- `s` **does not contain** any leading or trailing spaces.
- All the words in `s` are separated by a **single space**.

### Thoughts

> [!summary]
> This is a #string operation problem.

The main part is using two hash tables, to check for
mismatches, and using `istringstream` to read from string

Two hash tables:

- One is used to check for s has one and only bound word
- The other is used to check that the word is only stored
  once

Using one hash table is one way, which makes one way
unchecked.

### Solution

```cpp
class Solution {
public:
  bool wordPattern(string pattern, string s) {
    unordered_map<string, int> stoi;
    unordered_map<char, int> ctoi;
    // convert string to stream
    istringstream input(s);
    string word;
    int n = pattern.size();
    int id;

    for (id = 0; input >> word; id++) {
      // cout<<word<<'\n';
      if (id == n || stoi[word] != ctoi[pattern[id]]) {
        // pattern OOB, or mismatch.
        return false;
      }

      // to prevent id == 0 is the default value of map
      stoi[word] = ctoi[pattern[id]] = id + 1;
    }

    if (id == n) {
      return true;
    } else {
      // check for lingering word in s
      return false;
    }
  }
};
```