<p>Given a list of strings <code>words</code> and a string <code>pattern</code>, return <em>a list of</em> <code>words[i]</code> <em>that match</em> <code>pattern</code>. You may return the answer in <strong>any order</strong>.</p>

<p>A word matches the pattern if there exists a permutation of letters <code>p</code> so that after replacing every letter <code>x</code> in the pattern with <code>p(x)</code>, we get the desired word.</p>

<p>Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abc&quot;,&quot;deq&quot;,&quot;mee&quot;,&quot;aqq&quot;,&quot;dkd&quot;,&quot;ccc&quot;], pattern = &quot;abb&quot;
<strong>Output:</strong> [&quot;mee&quot;,&quot;aqq&quot;]
<strong>Explanation:</strong> &quot;mee&quot; matches the pattern because there is a permutation {a -&gt; m, b -&gt; e, ...}. 
&quot;ccc&quot; does not match the pattern because {a -&gt; c, b -&gt; c, ...} is not a permutation, since a and b map to the same letter.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;], pattern = &quot;a&quot;
<strong>Output:</strong> [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= pattern.length &lt;= 20</code></li>
	<li><code>1 &lt;= words.length &lt;= 50</code></li>
	<li><code>words[i].length == pattern.length</code></li>
	<li><code>pattern</code> and <code>words[i]</code> are lowercase English letters.</li>
</ul>

class Solution {
private:
    class entry {
    public:
        char    d;
        int     idx;

        entry() {
            d = '\0';
            idx = -1;
        }

        entry(char data, int index) {
            d = data;
            idx = index;
        }
    };

public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        int i, j;
        int idx1, idx2;
        int len;
        int n;
        vector<entry> inv;
        vector<entry> tbl;
        vector<string> res;

        tbl.resize(26);
        inv.resize(26);

        n = words.size();

        for (i = 0; i < n; i++) {
            string& word = words[i];

            len = word.length();
            j = 0;
            for (;;) {
                char c1, c2;

                c1 = word[j];
                c2 = pattern[j];
                idx1 = c1 - 'a';
                if (tbl[idx1].idx < i) {
                    idx2 = c2 - 'a';
                    if (inv[idx2].idx == i && inv[idx2].d != c1)
                        break;
                    tbl[idx1] = entry(c2, i);
                    inv[idx2] = entry(c1, i);
                } else if (tbl[idx1].d != c2)
                    break;
                ++j;
                if (j == len) {
                    res.push_back(word);
                    break;
                }
            }
        }

        return res;
    }
};
9700