原题链接:http://oj.leetcode.com/problems/interleaving-string/这是一道关于字符串操作的题目,要求是判断一个字符串能不能由两个字符串按照他们自己的顺序,每次挑取两个串中的一个字符来构造出来。像这种判断能否按照某种规则来完成求是否或者某个量的题目,很容易会想到用动态规划来实现。先说说维护量,res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出s3的前i+j个字符,如此最后结果就是res[s1.length()][s2.length()],判断是否为真即可。接下来就是递推式了,假设知道res[i][j]之前的所有历史信息,我们怎么得到res[i][j]。可以看出,其实只有两种方式来递推,一种是选取s1的字符作为s3新加进来的字符,另一种是选s2的字符作为新进字符。而要看看能不能选取,就是判断s1(s2)的第i(j)个字符是否与s3的i+j个字符相等。如果可以选取并且对应的res[i-1][j](res[i][j-1])也为真,就说明s3的i+j个字符可以被表示。这两种情况只要有一种成立,就说明res[i][j]为真,是一个或的关系。所以递推式可以表示成
res[i][j] = res[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)
时间上因为是一个二维动态规划,所以复杂度是O(m*n),m和n分别是s1和s2的长度。最后就是空间花费,可以看出递推式中只需要用到上一行的信息,所以我们只需要一个一维数组就可以完成历史信息的维护,为了更加优化,我们把短的字符串放在内层循环,这样就可以只需要短字符串的长度即可,所以复杂度是O(min(m,n))。代码如下:public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length())
return false;
String minWord = s1.length()>s2.length()?s2:s1;
String maxWord = s1.length()>s2.length()?s1:s2;
boolean[] res = new boolean[minWord.length()+1];
res[0] = true;
for(int i=0;i<minWord.length();i++)
{
res[i+1] = res[i] && minWord.charAt(i)==s3.charAt(i);
}
for(int i=0;i<maxWord.length();i++)
{
res[0] = res[0] && maxWord.charAt(i)==s3.charAt(i);
for(int j=0;j<minWord.length();j++)
{
res[j+1] = res[j+1]&&maxWord.charAt(i)==s3.charAt(i+j+1) || res[j]&&minWord.charAt(j)==s3.charAt(i+j+1);
}
}
return res[minWord.length()];
}
动态规划其实还是有套路的,无非就是找到维护量,然后得到递推式,接下来看看历史信息对于空间的需求,尽量优化,会在后面对于动态规划做一个比较通用的总结哈。
分享到:
相关推荐
leetcode 分类 ...Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
leetcode卡 OJ 题目汇总 记录下自己做过的oj题目, 也记录下自己对算法以及编程的理解与偏见. 杂感 算法到底是有用还是没用? 这个问题一直萦绕在我的心里. ...String动态规划解决, Recovering BST失败
"interleaving_string.erl","search_insert_position.erl", "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
Memory InterleavingNorman Matloff Department of Computer Science University of California at DavisNovember 5, 2003 ... Matloff1 IntroductionWith large memories, many memory chips must be assembled ...
无交织瑞利信道软解码的误码率
具有交织的瑞利信道硬解码的误码率
ITRI CIM Emulator能够读取SML档案,主要功能是用来测试半导体设备的通讯功能,它...Multi-Block Message Interleaving Send Non-ENQ Bad Length Byte Bad Checksum T1 Timeout T2 Timeout for Length Byte T4 Timeout
QPSK MODUALTION WITH HELICAL INTERLEAVING of OFDM sysytem BER-bit error rate analisys. and trying to improve more BER
Interleaving function using labview
A multi-focus optical fiber lens is numerically ... The spatial distribution of the dielectric resonators is dictated by spatial multiplexing, including interleaving meta-atoms and lens aperture divisio
Slice interleaving in compressed video packetization
OFDM全过程,包括卷积、交织、上下变频以及信道
语言:English 用Anki抽认卡替换新的标签页 通过将它们整合到您的浏览习惯中,可以使抽认卡的...取自2018年9月9日,来自https://www.scientificamerican.com/article/the-interleaving-effect-mixing-it-up-boosts-learn
Interleaving String Scramble String Minimum Path Sum Edit Distance Decode Ways Distinct Subsequences Word Break Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query...
Self-embedding fragile watermarking based on reference-data interleaving and adaptive selection of embedding mode
Downstream signal processing, synch, FEC, bit Mapping , interleaving, IDFT, CP
数据结构中用python实现两个单链表交叉插入,在LList类中
A 38.88 MHz time-stretch line-scan imaging system with parallel interleaving detection is experimentally demonstrated. Since only half-chromatic dispersion is used to stretch optical pulses for ...
AMR在IP域中的编码(rfc3267,4867) 缩写解释 SID Silence Descriptor (Comfort Noise Frame) 1 AMR编码介绍 AMR编码是一种自适应多速率编码,根据传输信道的实际情况,调整编码模式、速率和纠错码位数来保证...