首页 > 其他分享 >【刷题笔记】97. Interleaving String

【刷题笔记】97. Interleaving String

时间:2023-11-02 21:01:17浏览次数:35  
标签:p2 p1 String s3 s2 Interleaving visited s1 97

题目

Given strings s1s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

/i/li/?n=2&i=images/blog/202311/02203437_6543975d71cd564602.jpg?,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=

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

Example 2:

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

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

题目大意

给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

提示:a + b 意味着字符串 a 和 b 连接。

解题思路

  • 深搜或者广搜暴力解题。笔者用深搜实现的。记录 s1 和 s2 串当前比较的位置 p1 和 p2。如果 s3[p1+p2] 的位置上等于 s1[p1] 或者 s2[p2] 代表能匹配上,那么继续往后移动 p1 和 p2 相应的位置。因为是交错字符串,所以判断匹配的位置是 s3[p1+p2] 的位置。如果仅仅这么写,会超时,s1 和 s2 两个字符串重复交叉判断的位置太多了。需要加上记忆化搜索。可以用 visited[i][j] 这样的二维数组来记录是否搜索过了。笔者为了压缩空间,将 i 和 j 编码压缩到一维数组了。i * len(s3) + j 是唯一下标,所以可以用这种方式存储是否搜索过。具体代码见下面的实现。

代码

package leetcode

func isInterleave(s1 string, s2 string, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	visited := make(map[int]bool)
	return dfs(s1, s2, s3, 0, 0, visited)
}

func dfs(s1, s2, s3 string, p1, p2 int, visited map[int]bool) bool {
	if p1+p2 == len(s3) {
		return true
	}
	if _, ok := visited[(p1*len(s3))+p2]; ok {
		return false
	}
	visited[(p1*len(s3))+p2] = true
	var match1, match2 bool
	if p1 < len(s1) && s3[p1+p2] == s1[p1] {
		match1 = true
	}
	if p2 < len(s2) && s3[p1+p2] == s2[p2] {
		match2 = true
	}
	if match1 && match2 {
		return dfs(s1, s2, s3, p1+1, p2, visited) || dfs(s1, s2, s3, p1, p2+1, visited)
	} else if match1 {
		return dfs(s1, s2, s3, p1+1, p2, visited)
	} else if match2 {
		return dfs(s1, s2, s3, p1, p2+1, visited)
	} else {
		return false
	}
}

标签:p2,p1,String,s3,s2,Interleaving,visited,s1,97
From: https://blog.51cto.com/u_16110811/8154781

相关文章

  • P9740 「KDOI-06-J」ION 比赛 题解
    题目思路:先计算总分数\(sum\),\(c_i=\frac{100}{a_i}\)为每道题的每个测试点分数。如果总分数达到\(Au\)线,直接输出AlreadyAu.。否则计算到达\(Au\)线还需多少分\(p\),遍历所有题,求出每道题的失分,如果失分大于等于\(p\),则输出\(\lceil\frac{p}{c_i}\rceil\),即至......
  • P9779 [HUSTFC 2023] 不定项选择题
    不定项选择题思路啊,咱就是说这个题目描述是多么通俗易懂啊。我们可以知道,这道题是只有选或不选两种情况,就是问你有多少种情况,我们可以知道就是有\(2^n\)种情况,即(1<<n)种,但是题目中有一个情况不算,就是都不选的情况,所以我们最后要减\(1\)。即(1<<n)-1,这就是最后的公式。......
  • Strings of Impurity
    link不懂为什么都写平衡树,明明set就好了啊,思路跟平衡树差不多,实现起来较为简单。intn,m,k;ints[N];strings1,s2;intcnt[N];vector<int>t;set<int>p[N];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr); cin>>s1>>s2; n=s1.size()......
  • P4397聪明的燕姿 题解 & Miller~Rabin 质数判定
    涉及质数的时间复杂度都是玄学的。——题记传送门由整数唯一分解定理:\(\coprod\limits_{i=1}^{k}p_i^{c_i}\)有该正整数的正约数为:\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^j)\)即我们要求有多少个数满足\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^......
  • linux 中 strings命令
     001、linux中strings命令主要是在对象文件或者二进制文件中查找可打印的字符串。 002、举例(base)[b20223040323@admin1~]$strings/bin/ls|head/lib64/ld-linux-x86-64.so.2libselinux.so.1__gmon_start___initfgetfileconfreeconlgetfilecon_finilibc......
  • std::string_view
    在原来的string操作中,大多数都是复制string进行操作,如:substr()、string&传参。它们都会复制占用额外内存。使用std::string_view犹如只是对它的视图映射进行处理,有一个指针指向一个起始位置,然后会有一个size参数去决定这个指针的移动步数。#if1PrintName(std::string_viewstr......
  • 无涯教程-C语言 - 字符串(String)
    字符串实际上是由null字符'\0'终止的一维字符数组,因此,以零结尾的字符串包含由字符串组成的字符,后跟null。以下声明和初始化创建一个由单词"Hello"组成的字符串。chargreeting[6]={'H','e','l','l','o','\0'};如果您遵循数组初始化的规则,那么您可以编写以下语句,如下......
  • AH6971-9V-15v电压升降12V2A芯片解决方案:参数特性和应用领域
    9V-15V升降12V2A芯片解决方案:参数特性和应用领域随着科技的发展,各种智能设备的需求在不断增长,而电源作为智能设备的重要组成部分,其稳定性和效率直接影响着设备的性能。在此背景下,9V-15V升降12V2A芯片解决方案应运而生。参数特性:宽输入电压范围:5V~35V,能够适应多种电源环境。高效......
  • CF1889A. Qingshan Loves Strings 2
    不妨考虑什么时候会无解!显然当原序列\(0,1\)数量不同,或者序列总长为奇数时会无解!否则我们设\(l=1,r=n\)!开始回文配对!如果配上了就直接删掉!并把左右端点向内移动!如果两者都是\(0\),就在末尾加上\(01\)!都是\(1\)就加最前面!以在末尾加入举例!此时如果开头是\(01\)就会多......
  • ADASTRNG - Ada and Substring 题解
    ADASTRNG-AdaandSubstring题解题目描述给定一个小写字符串。输出\(26\)个数,代表以\(\texttt{a}\sim\texttt{z}\)开头的本质不同的子串个数。题目分析高度数组模板题。可以想到将以每个字符开头的本质不同的子串数目转化为:以每个字符开头的所有字串数目减去以每......