Dell Coding Questions and Answers

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

class Solution {
public:
    vector compute_lps(string& s, unordered_map<char, unordered_set>& m) {
    vector lps(s.size());
    for (int i = 1, j = 0; i < s.size(); ++i) {
        while (j && (s[i] != s[j] && m[s[i]].count(s[j]) == 0 && m[s[j]].count(s[i]) == 0))
            j = max(0, lps[j] - 1);
        j += s[i] == s[j] || m[s[i]].count(s[j]) || m[s[j]].count(s[i]);
        lps[i] = j;
    }
    return lps;
    }

    bool matchReplacement(string s, string sub, vector<vector>& mappings) {
        unordered_map<char, unordered_set> m;
        for (auto& p : mappings)
            m[p[0]].insert(p[1]);
        auto lps = compute_lps(sub, m);
        for (int i = 0, j = 0; i < s.size();) {
            if (s[i] == sub[j] || m[sub[j]].count(s[i])) {
                ++i;
                ++j;
            } else {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
            if (j == sub.size())
                return true;
        }
        return false;
    }
};

int main() {
    Solution solution;
    
    // Example usage:
    
    // string s = "fool3e7bar";
    // string sub = "leet";
    // vector<vector> mappings = {{'e','3'}, {'t','7'}, {'t','8'}};
    
    // string s = "fooleetbar";
    // string sub = "f00l";
    // vector<vector> mappings = {{'o','0'}};
    
    string s = "Fool33tbaR";
    string sub = "leetd";
    vector<vector> mappings = {{'e','3'}, {'t','7'}, {'t','8'}, {'d','b'}, {'p','b'}};
    
    bool result = solution.matchReplacement(s, sub, mappings);
    cout << boolalpha << result << endl;  // Output: true
    
    return 0;
}

class Solution:
    def compute_lps(self, s, m):
        lps = [0] * len(s)
        j = 0
        for i in range(1, len(s)):
            while j > 0 and (s[i] != s[j] and (s[i] not in m or s[j] not in m[s[i]])):
                j = lps[j - 1]
            j += int(s[i] == s[j] or (s[i] in m and s[j] in m[s[i]]))
            lps[i] = j
        return lps

    def matchReplacement(self, s, sub, mappings):
        m = {}
        for p in mappings:
            if p[0] not in m:
                m[p[0]] = set()
            m[p[0]].add(p[1])

        lps = self.compute_lps(sub, m)
        i, j = 0, 0
        while i < len(s):
            if s[i] == sub[j] or (sub[j] in m and s[i] in m[sub[j]]):
                i += 1
                j += 1
            else:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
            if j == len(sub):
                return True
        return False


solution = Solution()

# Example usage:
s = "fool3e7bar"
sub = "leet"
mappings = [['e', '3'], ['t', '7'], ['t', '8']]

# s = "fooleetbar"
# sub = "f00l"
# mappings = [['o', '0']]

# s = "Fool33tbaR"
# sub = "leetd"
# mappings = [['e', '3'], ['t', '7'], ['t', '8'], ['d', 'b'], ['p', 'b']]

result = solution.matchReplacement(s, sub, mappings)
print(result)  # Output: True

class Main {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        int m = sub.length(), n = s.length();
        final int RANGE = 'z' - '0' + 1;

        boolean[][] multiMap = new boolean[RANGE][RANGE];
        for (char[] map : mappings) {
            char from = map[0], to = map[1];
            multiMap[from - '0'][to - '0'] = true;
        }
        // Now, we use a naive string matching algorithm
        // This will run in O(mn) time.
        for (int i = 0; i < n - m + 1; i++) {
            int j = 0;
            while (j < m) {
                char sc = s.charAt(i + j), subc = sub.charAt(j);
                if (sc != subc && !multiMap[subc - '0'][sc - '0'])
                    break;
                j++;
            }
            if (j == m)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Main main = new Main();

        // Example usage:
        // String s = "fool3e7bar";
        // String sub = "leet";
        // char[][] mappings = { { 'e', '3' }, { 't', '7' }, { 't', '8' } };

        // String s = "fooleetbar";
        // String sub = "f00l";
        // char[][] mappings = { { 'o', '0' } };

        String s = "Fool33tbaR";
        String sub = "leetd";
        char[][] mappings = { { 'e', '3' }, { 't', '7' }, { 't', '8' }, { 'd', 'b' }, { 'p', 'b' } };

        boolean result = main.matchReplacement(s, sub, mappings);
        System.out.println(result); // Output: true
    }
}