Pattern matching coding pattern

10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/description/

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Approach 1: Recursion from right to left (with memoization)

1. We can establish recursion relationship, scanning from right to left.
2. Right to left helps to discover * earlier so that we can apply the match rule.
3. If we do left to right then we will have to look into future which break the train of thoughts.
4. Main reason is, with recursion, we try to focus on solving current problem without looking into future pattern.
5. With recursion, it is ok to look into past solved problem.

We can come up with following recurrence relationship.

f(i,j) = true/false if match with text index from 0 to i and pattern 0 to j
f(i,j) = false  if s[i] !== p[j] and  p[j] is not either . or *
f(i,j) = f(i-1, j-1) if (s[i] == p[j] || p[j] =='.')
f(i,j) = if p[j] is *, Or{  
         f(i, j-2), // choice for zero i.e. ignore prev char 
         (s[i] == p[j-1] || p[j-1] =='.') && f(i-1, j) // choice for one or more

Since there is repetition therefore we can apply memoization to speedup the recursion. Following is code for reference.

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const cache = new Array(m).fill(0).map(a => new Array(n).fill(-1));
    const recursion = (i, j) => {
        // Empty pattern
        if (j === -1) {
            return i === -1; // Can match with empty text
        }

        // Empty string
        if (i === -1) {
            if (j >= 0 && p[j] === '*') {
                // Ignore case for * i.e. zero match with prev char in pattern
                return recursion(i, j - 2);
            }
            return false;
        }
        if (cache[i][j] !== -1) {
            return cache[i][j];
        }

        // Choice: single char match
        if (s[i] === p[j] || p[j] === '.') {
            return cache[i][j] = recursion(i - 1, j - 1);
        }
        // Choice: * case
        if (p[j] === '*') {
            const zeroMatch = recursion(i, j - 2);
            const oneMatch = (s[i] === p[j - 1] || p[j - 1] === '.') && recursion(i - 1, j);
            const result = zeroMatch || oneMatch;
            return cache[i][j] = zeroMatch || oneMatch;
        }
        // If no match then return false
        return false;
    }
    return recursion(m - 1, n - 1);
};

Approach #2: Bottom up dynamic programming

1. dp[i][j] represents the match result true/false for the string of length i and pattern of length j
2. Since i & j represents the length therefore while checking the char, we need to use s[i-1] or p[j-1]
3. Since DP by default is right to left i.e. assumption is lower size problem is already solved and now working on largest size problem.
4. Rest is same as recursion approach

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const dp = new Array(m + 1).fill(0).map(a => new Array(n + 1).fill(false));
    // Base case 1: Both are empty
    dp[0][0] = true;

    // Base case 2: Text is empty
    for (let j = 1; j < n + 1; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2]; // use zero case i.e. ignore the prev char in pattern
        }
    }

    // Fill rest from left to right and top to bottom
    for (let i = 1; i < m + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
            if (s[i - 1] === p[j - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                const zeroOrMore = dp[i][j - 2];
                const prev = p[j - 2];
                const oneOrMore = (s[i - 1] === prev || prev === '.') && dp[i - 1][j];
                dp[i][j] = zeroOrMore || oneOrMore;
            }
        }
    }
    return dp[m][n];
};

44. Wildcard Matching

https://leetcode.com/problems/wildcard-matching/description/

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Approach 1: Recursion with memoization

This problem is almost similar as the previous one with difference of how * is treated.

Here * doesn’t have any dependency of matching with previous char. It means * comparison is independent. We will have just two choice with * , either ignore it or match with the text char.

Also, since * has no dependency therefore we can run recursion in any order i.e. either left to right or right to left processing.

Following is recursion relationship.

f(i, j) = True/false for s (0...i) and p(0...j)
f(i,j) = f(i-1, j-1) if (s[i] ==p[j] or p[j] ==?)
       = f(i-1, j) || f(i, j-1) if p[j] == *
       = false // Otherwise

Following is code for reference.

var usingRecursion = function (s, p) {
    const m = s.length;
    const n = p.length;
    const cache = new Array(m).fill(0).map(a => new Array(n).fill(-1));
    const recursion = (i, j) => {
        // Empty pattern
        if (j === -1) {
            return i === -1; // Can match with empty text
        }

        // Empty string
        if (i === -1) {
            if (j >= 0 && p[j] === '*') {
                // Ignore case for * i.e. zero match with char in pattern
                return recursion(i, j - 1);
            }
            return false;
        }
        if (cache[i][j] !== -1) {
            return cache[i][j];
        }

        // Choice: single char match
        if (s[i] === p[j] || p[j] === '?') {
            return cache[i][j] = recursion(i - 1, j - 1);
        }
        // Choice: * case
        if (p[j] === '*') {
            const zeroMatch = recursion(i, j - 1);
            const oneMatch = recursion(i - 1, j);
            const result = zeroMatch || oneMatch;
            return cache[i][j] = zeroMatch || oneMatch;
        }
        // If no match then return false
        return false;
    }
    return recursion(m - 1, n - 1);
};

Approach 2: Using bottom up dynamic programming

1. We can use the same relationship as we described with recursion approach.
2. dp[i][j] can be either true or false. Here i represent the length of string and similarly j represent the length of pattern.
3. This is the reason while reading the text or pattern we use i-1 or j-1 .

Following is code for reference.

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const dp = new Array(m + 1).fill(0).map(a => new Array(n + 1).fill(false));
    // Base case 1: Both are empty
    dp[0][0] = true;

    // Base case 2: Text is empty
    for (let j = 1; j < n + 1; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1]; // use zero case
        }
    }

    // Fill rest from left to right and top to bottom
    for (let i = 1; i < m + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
            if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                const zeroOrMore = dp[i][j - 1];
                const oneOrMore = dp[i - 1][j];
                dp[i][j] = zeroOrMore || oneOrMore;
            }
        }
    }
    return dp[m][n];
};

290. Word Pattern

https://leetcode.com/problems/word-pattern/description/

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.

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

Approach

We can maintain separate hash map for pattern and word and if there is cache hit then validate the pattern vice versa.

Following is code for reference.

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
    const wCache = new Map();
    const pCache = new Map();
    const words = s.split(' ');
    const m = pattern.length;
    const n = words.length;
    if (m !== n) {
        return false;
    }
    for (let i = 0; i < n; i++) {
        const word = words[i];
        const p = pattern[i];
        if (!wCache.has(word)) {
            // Word cache miss means therefore should be cache miss for pattern too 
            if (pCache.has(p)) {
                return false;
            }
            wCache.set(word, p);
            pCache.set(p, word);
        } else {
            // Cache hits on word, should match with the previous pattern
            if (wCache.get(word) !== p) {
                return false;
            }
            if (pCache.get(p) !== word) {
                return false;
            }
        }
    }
    return true;
};

291. Word Pattern II

https://leetcode.com/problems/word-pattern-ii/description/

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"

Example 3:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false

Approach: Hashmap with backtrack

1. Create a hash map symbolMap that maps the key, a character from pattern, to the value, a substring of s.
2. Create a hash set wordSet that stores the unique substrings of s that have been mapped to a symbol.
3. Use backtrack approach to try all possible value for pattern and return answer.

Following is code for reference.

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPatternMatch = function (pattern, s) {
    const m = pattern.length;
    const n = s.length;
    const map = new Map();
    const set = new Set();
    const recursion = (i, j) => {
        // base case: empty pattern and and s
        if (i === m && j === n) {
            return true;
        }
        // base case: one of pattern or s is empty
        if (i === m || j === n) {
            return false;
        }
        const p = pattern[i];

        // if pattern exist in map
        if (map.get(p)) {
            const pMatch = map.get(p);

            // process next substring of s of length pattern p
            const word = s.substring(j, j + pMatch.length);

            // if not match then return false
            if (word !== pMatch) {
                return false;
            }

            // try next pattern and word
            return recursion(i + 1, j + pMatch.length);
        }
        // pattern doesn't exist, need to try all possible token
        for (let k = j; k < n; k++) {
            const pMatch = s.substring(j, k + 1);
            // if duplicate token then skip i.e. try next option
            if (set.has(pMatch)) {
                continue;
            }

            // add into set and map
            set.add(pMatch);
            map.set(p, pMatch);

            // Recurse rest and return early
            if (recursion(i + 1, k + 1)) {
                return true;
            }

            // backtrack set and map
            set.delete(pMatch);
            map.delete(p);
        }
        return false;
    }
    return recursion(0, 0);
};

890. Find and Replace Pattern

https://leetcode.com/problems/find-and-replace-pattern/description/

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

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

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.

Example 1:

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

Approach

1. Build trie for given words
2. Maintain wMap & pMap to traverse each level
3. On backtrack remove entries from these maps.
4. Simple would be to create a copy of map, but it would take lot of spaces
5. Capture the word if it matches to the pattern.
6. Note: To return the duplicate word as an answer, we will need to keep array of words at word node.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
        this.words = [];
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    add(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
        node.words.push(word);
    }
    search(pattern, ans) {
        const wMap = new Map();
        const pMap = new Map();
        this.dfs(pattern, pMap, wMap, 0, ans, this.root);
    }
    getNeighbors(node) {
        return node.children.filter(child => child);
    }
    dfs(pattern, pMap, wMap, i, ans, node) {
        const n = pattern.length;
        // Check for answer
        if (i === n && node.isWord) {
            ans.push(...node.words);
            return;
        }
        // if pattern is empty
        if (i === n) {
            return;
        }
        const p = pattern[i];
        // Get all neighbors
        for (const child of this.getNeighbors(node)) {
            const w = child.chr;
            // if new pattern char
            if (!pMap.has(p)) {
                // corresponding word char should also be new
                if (wMap.has(w)) {
                    // skip this word char
                    continue;
                }
                // process it
                pMap.set(p, w);
                wMap.set(w, p);
                this.dfs(pattern, pMap, wMap, i + 1, ans, child);
                // back track
                pMap.delete(p);
                wMap.delete(w);
            } else {
                // existing pattern char
                if (pMap.get(p) !== w || wMap.get(w) !== p) {
                    // corresponding word char should also exist and same
                    continue;
                }
                this.dfs(pattern, pMap, wMap, i + 1, ans, child);
            }
        }
    }
}
const buildTrie = words => {
    const trie = new Trie();
    for (const word of words) {
        trie.add(word);
    }
    return trie;
}
/**
 * @param {string[]} words
 * @param {string} pattern
 * @return {string[]}
 */
var findAndReplacePattern = function (words, pattern) {
    const trie = buildTrie(words);
    const ans = [];
    trie.search(pattern, ans);
    return ans;
};

686. Repeated String Match

https://leetcode.com/problems/repeated-string-match/description/

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b​​​​​​ to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".

Example 1:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Approach

1. Any string of same size a & b, a+a will have substring. if not then not possible
2. m >=2n then compare only once.
3. Otherwise try all possible.

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function (a, b) {
    const m = a.length;
    const n = b.length;

    let size = 0;
    let token = '';
    let ans = 0;

    while (ans <= 2 || size <= 2 * n) {
        token += a;
        ans++;
        size += m;
        if (token.indexOf(b) >= 0) {
            return ans;
        }
    }
    return -1;
};

925. Long Pressed Name

https://leetcode.com/problems/long-pressed-name/description/

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function (name, typed) {
    /**
     name  = aleex
     typed = aaaaaaleex
     */
    const m = name.length;
    const n = typed.length;
    let i = 0;
    let j = 0;
    while (i < m && j < n) {
        if (name[i] === typed[j]) {
            i++;
            j++;
        } else {
            // keep skipping typed char same as left
            while (j > 0 && typed[j - 1] === typed[j]) {
                j++;
            }
            // Now if char didn't match then false
            if (name[i] !== typed[j]) {
                return false;
            }
            i++;
            j++;
        }
    }
    // skip typed if same as last char
    while (j > 0 && typed[j - 1] === typed[j]) {        
        j++;
    }
    return i === m && j === n;
};

468. Validate IP Address

https://leetcode.com/problems/validate-ip-address/description/

Given a string queryIP, return "IPv4" if IP is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.

A valid IPv4 address is an IP in the form "x1.x2.x3.x4" where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses while "192.168.01.1", "192.168.1.00", and "192.168@1.1" are invalid IPv4 addresses.

A valid IPv6 address is an IP in the form "x1:x2:x3:x4:x5:x6:x7:x8" where:

• 1 <= xi.length <= 4
• xi is a hexadecimal string which may contain digits, lowercase English letter ('a' to 'f') and upper-case English letters ('A' to 'F').
• Leading zeros are allowed in xi.

For example, “2001:0db8:85a3:0000:0000:8a2e:0370:7334" and "2001:db8:85a3:0:0:8A2E:0370:7334" are valid IPv6 addresses, while "2001:0db8:85a3::8A2E:037j:7334" and "02001:0db8:85a3:0000:0000:8a2e:0370:7334" are invalid IPv6 addresses.

Example 1:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: queryIP = "256.256.256.256"
Output: "Neither"
Explanation: This is neither a IPv4 address nor a IPv6 address.

Constraints:

• queryIP consists only of English letters, digits and the characters '.' and ':'.

Approach: Use Regex

IPV4 Regex:

1. Chunk contains only one digit, from 0 to 9 i.e. [0-9].
2. Chunk contains two digits. The first one could be from 1 to 9, and the second one from 0 to 9 i.e. [1–9][0-9].
3. Chunk contains three digits, and the first one is 1. The second and the third ones could be from 0 to 9 i.e. [1][0–9][0–9].
4. Chunk contains three digits, the first one is 2 and the second one is from 0 to 4. Then the third one could be from 0 to 9 i.e [2][0–4][0–9].
5. Chunk contains three digits, the first one is 2, and the second one is 5.
   Then the third one could be from 0 to 5 i.e. [2][5][0–5].
6. Let’s use | to implement or condition.
7. Let’s use {x} to impelement repeated x times.

This will give us following regex

const ipv4 = /^(([0-9]|[1-9][0-9]|1[0-9][0-9]|2([0-4][0-9]|5[0-5]))\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2([0-4][0-9]|5[0-5]))$/;
const ipv6 = /^([0-9a-fA-F]{1,4}:){7}([0-9a-fA-F]{1,4})$/;

Following is code for reference.

/**
 * @param {string} IP
 * @return {string}
 */
var validIPAddress = function(IP) {
    /**
    IPV4: [0-255].[0-255].[0-255]
    0-255 - {0-9}, {10, 99}, {100, 199} {200, 255}
        [0-9]|[1-9][0-9]|[1][0-9][0-9]|[2][0-5][0-5]
    IPV6: [0-FFFF]:[0-FFFF]:[0-FFFF]:[0-FFFF]:[0-FFFF]:[0-FFFF]:[0-FFFF]:     [0-FFFF]
        ([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}
    */
    const ipv4 = /^(([0-9]|[1-9][0-9]|1[0-9][0-9]|2([0-4][0-9]|5[0-5]))\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2([0-4][0-9]|5[0-5]))$/;
    const ipv6 = /^([0-9a-fA-F]{1,4}:){7}([0-9a-fA-F]{1,4})$/;
    return ipv4.test(IP) ? 'IPv4' : ipv6.test(IP) ? 'IPv6' : 'Neither';
};

Happy coding :-)