LeetCode-Interleaving String

￡神魔★判官ぃ 2022-08-04 12:58 75阅读 0赞

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

For example,  
Given:  
s1 = `"aabcc"`,  
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.  
When s3 = `"aadbbbaccc"`, return false.

又是一个关于字符串的动态规划题，[Distinct Subsequences][]、[Edit Distance][]都差不多，肯定回溯法是可以解出来的，但是肯定时间复杂度比较高。这时候想起来动态规划算法。分析基本跟上述两个问题的方式是一样的。

还是看住最后一个字符s1\[j\], s2\[i\]与s3\[i+j-1\]之间的关系，代码见下：

public boolean isInterleave(String s1, String s2, String s3) {
        	if (s1.length() + s2.length() != s3.length()) return false;
            boolean[][] dp = new boolean[s2.length()+1][s1.length()+1];
            
            dp[0][0] = true;
            for (int i = 1; i < dp[0].length; i++) {
            	dp[0][i] = s1.charAt(i-1) == s3.charAt(i-1) && dp[0][i-1];
            }
            
            for (int i = 1; i < dp.length; i++) {
            	dp[i][0] = s2.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0];
            }
            for (int i = 1; i < dp.length; i++) {
            	for (int j = 1; j < dp[i].length; j++) {
            		dp[i][j] = (s3.charAt(i+j-1) == s1.charAt(j-1) && dp[i][j-1]) 
            				|| (s3.charAt(i+j-1) == s2.charAt(i-1) && dp[i-1][j]);
            	}
            }
            return dp[s2.length()][s1.length()];
        }

[Distinct Subsequences]: http://blog.csdn.net/my_jobs/article/details/48052501
[Edit Distance]: http://blog.csdn.net/my_jobs/article/details/48032665

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关 String==new String吗

者在之前的面试被询问到 String a = "abc"; String b = "abc"; b = new String ("abc"); ...

一时失言乱红尘/ 2024年04月19日 09:36/ 0 赞/ 30 阅读

相关 String转换JAXBElement＜String＞

> String rec; > ObjectFactory objFac=new ObjectFactory(); > //其中createlkm是objFac的方法，

比眉伴天荒/ 2024年04月06日 14:28/ 0 赞/ 28 阅读

相关 Map＜String,String[]＞转换成＜String,Object＞

import java.util.HashMap; import java.util.Map; import java.util.Set;

小灰灰/ 2024年03月29日 15:41/ 0 赞/ 48 阅读

相关 String ，String[] ，List＜ String＞互转

String，String\[\]互转 // String → String[] String str = "1,2,3,4,5"; String

ゝ一世哀愁。/ 2024年03月23日 10:17/ 0 赞/ 58 阅读

相关 Map＜String,List＜String＞＞

List<Map<String,String>> jiaoXueJiHuaList = testMapper.selectJiaoXueJiHuaList();

心已赠人/ 2022年10月12日 01:32/ 0 赞/ 120 阅读

相关 Shell 字符串截取：${varible##string} ${varible#string} ${varible%%string} ${varible%string}

%%: 删除后面符合条件的最长字符串 [shengshu@shuai shell-dir]$ var="xyz=123=456"; val=${var%%[=]

忘是亡心i/ 2022年08月07日 16:45/ 0 赞/ 137 阅读

相关 Map<String,String> colMap = new HashMap<String,String>();和HashMap<String,String> colMap =Map和HashMap

要搞清楚这个事情你就首先得搞清楚Java里面的一件事情那就是三大特性里面的多态性，什么是多态性，所谓的多态性就是多态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发

浅浅的花香味﹌/ 2022年06月09日 06:08/ 0 赞/ 192 阅读

相关 ListString, String>> 转 Map<String, List<String>>

将List转成Map结构，以下为没有水平的写法！好久之前写的土方法转换，不知道有没有优秀的解法，还希望大家提供！ Map<String, String> map1

灰太狼/ 2022年05月13日 02:58/ 0 赞/ 310 阅读

相关 String,String Buffer,String Build

可变性　简单的来说：String 类中使用 final 关键字字符数组保存字符串，`private　final　char　value[]`，所以 String 对象是不可

﹏ヽ暗。殇╰゛Y/ 2022年03月08日 21:28/ 0 赞/ 223 阅读

相关 IEnumberable<String> To String

如何根据关键字在List<T>中查询出来相应的结果？ Code: Create List<T> public class A \{ public string

快来打我*/ 2021年12月20日 11:11/ 0 赞/ 241 阅读