match-substring-after-replacement

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two strings <code>s</code> and <code>sub</code>. You are also given a 2D character array <code>mappings</code> where <code>mappings[i] = [oldi, newi]</code> indicates that you may perform the following operation any number of times:

<ul>
	<li>Replace a character <code>oldi</code> of <code>sub</code> with <code>newi</code>.</li>
</ul>

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

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

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

&nbsp;
Example 1:

<pre>
Input: s = &quot;fool3e7bar&quot;, sub = &quot;leet&quot;, mappings = [[&quot;e&quot;,&quot;3&quot;],[&quot;t&quot;,&quot;7&quot;],[&quot;t&quot;,&quot;8&quot;]]
Output: true
Explanation: Replace the first &#39;e&#39; in sub with &#39;3&#39; and &#39;t&#39; in sub with &#39;7&#39;.
Now sub = &quot;l3e7&quot; is a substring of s, so we return true.</pre>

Example 2:

<pre>
Input: s = &quot;fooleetbar&quot;, sub = &quot;f00l&quot;, mappings = [[&quot;o&quot;,&quot;0&quot;]]
Output: false
Explanation: The string &quot;f00l&quot; is not a substring of s and no replacements can be made.
Note that we cannot replace &#39;0&#39; with &#39;o&#39;.
</pre>

Example 3:

<pre>
Input: s = &quot;Fool33tbaR&quot;, sub = &quot;leetd&quot;, mappings = [[&quot;e&quot;,&quot;3&quot;],[&quot;t&quot;,&quot;7&quot;],[&quot;t&quot;,&quot;8&quot;],[&quot;d&quot;,&quot;b&quot;],[&quot;p&quot;,&quot;b&quot;]]
Output: true
Explanation: Replace the first and second &#39;e&#39; in sub with &#39;3&#39; and &#39;d&#39; in sub with &#39;b&#39;.
Now sub = &quot;l33tb&quot; is a substring of s, so we return true.

</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= sub.length &lt;= s.length &lt;= 5000</code></li>
	<li><code>0 &lt;= mappings.length &lt;= 1000</code></li>
	<li><code>mappings[i].length == 2</code></li>
	<li><code>oldi != newi</code></li>
	<li><code>s</code> and <code>sub</code> consist of uppercase and lowercase English letters and digits.</li>
	<li><code>oldi</code> and <code>newi</code> are either uppercase or lowercase English letters or digits.</li>
</ul>

matchReplacement

Match Substring After Replacement

Design Add and Search Words Data Structure

design-add-and-search-words-data-structure

添加与搜索单词 - 数据结构设计

Number of Subarrays That Match a Pattern II

number-of-subarrays-that-match-a-pattern-ii

匹配模式数组的子数组数目 II

Array

Hash Table

String

String Matching

给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>sub</code>&nbsp;。同时给你一个二维字符数组&nbsp;<code>mappings</code> ，其中&nbsp;<code>mappings[i] = [oldi, newi]</code>&nbsp;表示你可以将&nbsp;<code>sub</code>&nbsp;中任意数目的&nbsp;<code>oldi</code>&nbsp;字符替换为&nbsp;<code>newi</code>&nbsp;。<code>sub</code>&nbsp;中每个字符 不能&nbsp;被替换超过一次。

如果使用 <code>mappings</code>&nbsp;替换 0 个或者若干个字符，可以将 <code>sub</code>&nbsp;变成 <code>s</code>&nbsp;的一个子字符串，请你返回&nbsp;<code>true</code>，否则返回&nbsp;<code>false</code>&nbsp;。

一个 子字符串&nbsp;是字符串中连续非空的字符序列。

&nbsp;

示例 1：

<pre>
输入：s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
输出：true
解释：将 sub 中第一个 'e' 用 '3' 替换，将 't' 用 '7' 替换。
现在 sub = "l3e7" ，它是 s 的子字符串，所以我们返回 true 。</pre>

示例 2：

<pre>
输入：s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
输出：false
解释：字符串 "f00l" 不是 s 的子串且没有可以进行的修改。
注意我们不能用 'o' 替换 '0' 。
</pre>

示例 3：

<pre>
输入：s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
输出：true
解释：将 sub 里第一个和第二个 'e' 用 '3' 替换，用 'b' 替换 sub 里的 'd' 。
得到 sub = "l33tb" ，它是 s 的子字符串，所以我们返回 true 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= sub.length &lt;= s.length &lt;= 5000</code></li>
	<li><code>0 &lt;= mappings.length &lt;= 1000</code></li>
	<li><code>mappings[i].length == 2</code></li>
	<li><code>oldi != newi</code></li>
	<li><code>s</code> 和&nbsp;<code>sub</code>&nbsp;只包含大写和小写英文字母和数字。</li>
	<li><code>oldi</code> 和&nbsp;<code>newi</code>&nbsp;是大写、小写字母或者是个数字。</li>
</ul>