C++实现LeetCode(97.交织相错的字符串)

[LeetCode] 97.Interleaving String 交织相错的字符串

Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

这道求交织相错的字符串和之前那道 Word Break 的题很类似,就像我之前说的只要是遇到字符串的子序列或是匹配问题直接就上动态规划 Dynamic Programming,其他的都不要考虑,什么递归呀的都是浮云(当然带记忆数组的递归写法除外,因为这也可以算是 DP 的一种),千辛万苦的写了递归结果拿到 OJ 上妥妥 Time Limit Exceeded,能把人气昏了,所以还是直接就考虑 DP 解法省事些。一般来说字符串匹配问题都是更新一个二维 dp 数组,核心就在于找出状态转移方程。那么我们还是从题目中给的例子出发吧,手动写出二维数组 dp 如下:

  Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T

首先,这道题的大前提是字符串 s1 和 s2 的长度和必须等于 s3 的长度,如果不等于,肯定返回 false。那么当 s1 和 s2 是空串的时候,s3 必然是空串,则返回 true。所以直接给 dp[0][0] 赋值 true,然后若 s1 和 s2 其中的一个为空串的话,那么另一个肯定和 s3 的长度相等,则按位比较,若相同且上一个位置为 True,赋 True,其余情况都赋 False,这样的二维数组 dp 的边缘就初始化好了。下面只需要找出状态转移方程来更新整个数组即可,我们发现,在任意非边缘位置 dp[i][j] 时,它的左边或上边有可能为 True 或是 False,两边都可以更新过来,只要有一条路通着,那么这个点就可以为 True。那么我们得分别来看,如果左边的为 True,那么我们去除当前对应的 s2 中的字符串 s2[j - 1] 和 s3 中对应的位置的字符相比(计算对应位置时还要考虑已匹配的s1中的字符),为 s3[j - 1 + i], 如果相等,则赋 True,反之赋 False。 而上边为 True 的情况也类似,所以可以求出状态转移方程为:

dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);

其中 dp[i][j] 表示的是 s2 的前 i 个字符和 s1 的前 j 个字符是否匹配 s3 的前 i+j 个字符,根据以上分析,可写出代码如下:

解法一:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1));
        dp[0][0] = true;
        for (int i = 1; i <= n1; ++i) {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n2; ++i) {
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
            }
        }
        return dp[n1][n2];
    }
};

我们也可以把for循环合并到一起,用if条件来处理边界情况,整体思路和上面的解法没有太大的区别,参见代码如下:

解法二:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1, false));
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= n2; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

这道题也可以使用带优化的 DFS 来做,我们使用一个 HashSet,用来保存匹配失败的情况,我们分别用变量i,j,和k来记录字符串 s1,s2,和 s3 匹配到的位置,初始化的时候都传入0。在递归函数中,首先根据i和j,算出 key 值,由于我们的 HashSet 中只能放一个数字,而我们要 encode 两个数字i和j,所以通过用i乘以 s3 的长度再加上j来得到 key,此时我们看,如果 key 已经在集合中,直接返回 false,因为集合中存的是无法匹配的情况。然后先来处理 corner case 的情况,如果i等于 s1 的长度了,说明 s1 的字符都匹配完了,此时 s2 剩下的字符和 s3 剩下的字符可以直接进行匹配了,所以我们直接返回两者是否能匹配的 bool 值。同理,如果j等于 s2 的长度了,说明 s2 的字符都匹配完了,此时 s1 剩下的字符和 s3 剩下的字符可以直接进行匹配了,所以我们直接返回两者是否能匹配的 bool 值。如果 s1 和 s2 都有剩余字符,那么当 s1 的当前字符等于 s3 的当前字符,那么调用递归函数,注意i和k都加上1,如果递归函数返回 true,则当前函数也返回 true;还有一种情况是,当 s2 的当前字符等于 s3 的当前字符,那么调用递归函数,注意j和k都加上1,如果递归函数返回 true,那么当前函数也返回 true。如果匹配失败了,则将 key 加入集合中,并返回 false 即可,参见代码如下:

解法三:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        unordered_set<int> s;
        return helper(s1, 0, s2, 0, s3, 0, s);
    }
    bool helper(string& s1, int i, string& s2, int j, string& s3, int k, unordered_set<int>& s) {
        int key = i * s3.size() + j;
        if (s.count(key)) return false;
        if (i == s1.size()) return s2.substr(j) == s3.substr(k);
        if (j == s2.size()) return s1.substr(i) == s3.substr(k);
        if ((s1[i] == s3[k] && helper(s1, i + 1, s2, j, s3, k + 1, s)) ||
            (s2[j] == s3[k] && helper(s1, i, s2, j + 1, s3, k + 1, s))) return true;
        s.insert(key);
        return false;
    }
};

既然 DFS 可以,那么 BFS 也就坐不住了,也要出来浪一波。这里我们需要用队列 queue 来辅助运算,如果将解法一讲解中的那个二维 dp 数组列出来的 TF 图当作一个迷宫的话,那么 BFS 的目的就是要从 (0, 0) 位置找一条都是T的路径通到 (n1, n2) 位置,这里我们还要使用 HashSet,不过此时保存到是已经遍历过的位置,队列中还是存 key 值,key 值的 encode 方法跟上面 DFS 解法的相同,初始时放个0进去。然后我们进行 while 循环,循环条件除了q不为空,还有一个是k小于 n3,因为匹配完 s3 中所有的字符就结束了。然后由于是一层层的遍历,所以要直接循环 queue 中元素个数的次数,在 for 循环中,对队首元素进行解码,得到i和j值,如果i小于 n1,说明 s1 还有剩余字符,如果 s1 当前字符等于 s3 当前字符,那么把 s1 的下一个位置 i+1 跟j一起加码算出 key 值,如果该 key 值不在于集合中,则加入集合,同时加入队列 queue 中;同理,如果j小于 n2,说明 s2 还有剩余字符,如果 s2 当前字符等于 s3 当前字符,那么把 s2 的下一个位置 j+1 跟i一起加码算出 key 值,如果该 key 值不在于集合中,则加入集合,同时加入队列 queue 中。for 循环结束后,k自增1。最后如果匹配成功的话,那么 queue 中应该只有一个 (n1, n2) 的 key 值,且k此时等于 n3,所以当 queue 为空或者k不等于 n3 的时候都要返回 false,参见代码如下:

解法四:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0;
        unordered_set<int> s;
        queue<int> q{{0}};
        while (!q.empty() && k < n3) {
            int len = q.size();
            for (int t = 0; t < len; ++t) {
                int i = q.front() / n3, j = q.front() % n3; q.pop();
                if (i < n1 && s1[i] == s3[k]) {
                    int key = (i + 1) * n3 + j;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
                if (j < n2 && s2[j] == s3[k]) {
                    int key = i * n3 + j + 1;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
            }
            ++k;
        }
        return !q.empty() && k == n3;
    }
};

到此这篇关于C++实现LeetCode(97.交织相错的字符串)的文章就介绍到这了,更多相关C++实现交织相错的字符串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-17

C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

C++实现LeetCode(187.求重复的DNA序列)

[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

C++实现LeetCode(87.搅乱字符串)

[LeetCode] 87. Scramble String 搅乱字符串 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great":     great /    \ gr    eat / \    /  \

C++实现LeetCode(86.划分链表)

[LeetCode] 86.Partition List 划分链表 Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions

C++实现LeetCode(89.格雷码)

[LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

C++实现LeetCode(91.解码方法)

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

C++实现LeetCode(136.单独的数字)

[LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

jquery+php实现滚动的数字特效

有时我们需要动态的展示访问次数.下载次数等效果,我们可以借助jQuery结合后台php实现一个滚动的数字展示效果. 本文以实时获取某产品的下载次数为场景,前台定时执行javascript获取最新的下载次数,并滚动更新页面上的下载次数. HTML 我们首先载入jQuery库文件和动画背景插件:animateBackground-plugin.js. <script type="text/javascript" src="js/jquery.js"><

Windows Powershell属性:描述对象是什么

属性可以描述一个对象,对象的属性可以被Powershell自动转换成文本,并且输出到控制台.因此可以通过这种方法查看任何对象,例如$host: 复制代码 代码如下: PS C:Powershell> $host Name              : ConsoleHost Version           : 2.0 InstanceId            : 7fefa1fa-fb2e-47c7-a867-c13b123da5c2 UI                : System.

使用apply方法处理数组的三个技巧[译]

apply方法 apply是所有函数都有的方法.它的签名如下: func.apply(thisValue, [arg1, arg2, ...]) 如果不考虑thisValue的影响,上面的调用等同于: func(arg1, arg2, ...) 也就是说,apply允许我们将一个数组"解开"成为一个个的参数再传递给调用函数.让我们分别看看apply使用中的三个技巧. 技巧1: 将一个数组传递给一个不接受数组作为参数的函数 JavaScript中没有返回一个数组中最大值的函数.但是,有一

详解SQLite中的查询规划器

 1.0 介绍 查询规划器的任务是找到最好的算法或者说"查询计划"来完成一条SQL语句.早在SQLite 3.8.0版本,查询规划器的组成部分已经被重写使它可以运行更快并且生成更好的查询计划.这种重写被称作"下一代查询规划器"或者"NGQP". 这篇文章重新概括了查询规划的重要性,提出来一些查询规划固有的问题,并且概括了NGQP是如何解决这些问题. 我们知道的是,NGQP(下一代查询规划器)几乎总是比旧版本的查询规划器好.然而,也许有的应用程序在

Android解析json数组对象的方法及Apply和数组的三个技巧

json是种常用的数据传输格式,在android开发中,如何借助java语言实现对json数组对象的解析呢,请参阅下面的关键代码: import org.json.JSONArray; import org.json.JSONObject; //jsonData的数据格式:[{ "id": "27JpL~jd99w9nM01c000qc", "version": "abc" },{ "id": "

解析PHP强制转换类型及远程管理插件的安全隐患

远程管理插件是目前广受WordPress站点管理员欢迎的实用工具,它允许用户同时对多个站点执行相同的操作,如更新到最新的发行版或安装插件等.但是,为了实现这些操作,客户端插件需要赋予远程用户很大的权限.因此,确保管理服务器和客户端插件之间的通信安全且不能被攻击者伪造就变得相当重要了.本文浅析几款可用插件,利用其弱点,攻击者甚至可以完全危及到运行这些插件的站点本身. ManageWP, InfiniteWP, and CMS Commander 这三个服务有着相同的客户端插件基础代码(目测最初是M

Vue路由之JWT身份认证的实现方法

一.JWT身份认证简介 JSON Web Token(JWT)是目前最流行的跨域身份验证解决方案,相较于session机制,服务器就不需要保存任何 session 数据了,也就是说,服务器变成无状态了,从而比较容易实现扩展.JWT 实际上是一个令牌(Token),服务器会将一些元数据.指定的secret进行签名并生成token,并返回给客户端,客户端得到这个服务器返回的令牌后,需要将其存储到 Cookie 或 localStorage 中,此后,每次与服务器通信都要带上这个令牌,可以把它放到 C

mongodb 数据类型(null/字符串/数字/日期/内嵌文档/数组等)

MongoDB的文档类似于JSON,JSON只是一种简单的表示数据的方式,只包含了6种数据类型(null.布尔.数字.字符串.数组及对象). JSON的数据类型的局限性: 1.无日期类型,对日期型的处理较为繁琐 2.无法区分浮点数和整数.32位和64位 3.其他类型表示局限 如函数.正则式等 Mongodb使用BSON(Binary JSON)来组织数据,BSON还提供日期.32位数字.64位数字等类型.下面为在mongodb shell中这些类型在文档中是如何表示: 1.null  用于表示空

js限制文本框只能输入数字方法小结

有时需要限制文本框输入内容的类型,本节分享下正则表达式限制文本框只能输入数字.小数点.英文字母.汉字等代码. 例如,输入大于0的正整数 复制代码 代码如下: <input onkeyup="if(this.value.length==1){this.value=this.value.replace(/[^1-9]/g,'')}else{this.value=this.value.replace(/\D/g,'')}" onafterpaste="if(this.valu

利用Python的Flask框架来构建一个简单的数字商品支付解决方案

作为一个程序员,我有时候忘了自己所具有的能力.当事情没有按照你想要的方式发展时,却很容易忘记你有能力去改变它.昨天,我意识到,我已经对我所出售的书的付款处理方式感到忍无可忍了.我的书完成后,我使用了三个不同的数字商品支付处理器,在对它们三个都感到不满后,我用Python和Flask,两个小时的时间写出了我自己的解决方案.没错!两个小时!现在,这个系统支撑着我的书籍付费流程,整个过程难以置信的简单,你可以在20秒内购买书籍并开始阅读. 往下看,看我是如何在一夜之间完成我自己的数字商品支付解决方案的