2301-MatchSubstringAfterReplacement.go

package main

// 2301. Match Substring After Replacement
// You are given two strings s and sub. 
// You are also given a 2D character array mappings where mappings[i] = [oldi, newi] indicates 
// that you may perform the following operation any number of times:
//     Replace a character oldi of sub with newi.

// Each character in sub cannot be replaced more than once.

// Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. 
// Otherwise, return false.

// A substring is a contiguous non-empty sequence of characters within a string.

// Example 1:
// Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
// Output: true
// Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
// Now sub = "l3e7" is a substring of s, so we return true.

// Example 2:
// Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
// Output: false
// Explanation: The string "f00l" is not a substring of s and no replacements can be made.
// Note that we cannot replace '0' with 'o'.

// Example 3:
// Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
// Output: true
// Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
// Now sub = "l33tb" is a substring of s, so we return true.

// Constraints:
//     1 <= sub.length <= s.length <= 5000
//     0 <= mappings.length <= 1000
//     mappings[i].length == 2
//     oldi != newi
//     s and sub consist of uppercase and lowercase English letters and digits.
//     oldi and newi are either uppercase or lowercase English letters or digits.

import "fmt"

func matchReplacement(s string, sub string, mappings [][]byte) bool {
    reachable := make([][]bool, 128)
    for i := range reachable {
        reachable[i] = make([]bool, 128)
    }
    for _, m := range mappings {
        reachable[m[0]][m[1]] = true
    }
    for i := 0; i < 128; i++ {
        reachable[i][i] = true
    }
    for i := 0; i < len(s)-len(sub)+1; i++ {
        for j := 0; j < len(sub) && reachable[sub[j]][s[i+j]]; j++ {
            if j == len(sub) - 1 {
                return true
            }
        }
    }
    return false
}

func main() {
    // Example 1:
    // Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
    // Output: true
    // Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
    // Now sub = "l3e7" is a substring of s, so we return true.
    fmt.Println(matchReplacement("fool3e7bar", "leet", [][]byte{{'e','3'},{'t','7'},{'t','8'}})) // true
    // Example 2:
    // Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
    // Output: false
    // Explanation: The string "f00l" is not a substring of s and no replacements can be made.
    // Note that we cannot replace '0' with 'o'.
    fmt.Println(matchReplacement("fooleetbar", "f00l", [][]byte{{'o','0'}})) // false
    // Example 3:
    // Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
    // Output: true
    // Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
    // Now sub = "l33tb" is a substring of s, so we return true.
    fmt.Println(matchReplacement("Fool33tbaR", "leetd", [][]byte{{'e','3'},{'t','7'},{'t','8'},{'d','b'},{'p','b'}})) // true
}