資訊專欄INFORMATION COLUMN
摘要：和一樣給出和兩種方法。使用可以避免初始化的和結(jié)果的混淆。
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.
和edit distance一樣給出dp和memorized search兩種方法。memorized search速度更快。
public boolean isInterleave(String s1, String s2, String s3) {
if ((s1.length()+s2.length())!=s3.length()) return false;
boolean[][] matrix = new boolean[s2.length()+1][s1.length()+1];
matrix[0][0] = true;
for (int i = 1; i < matrix[0].length; i++){
matrix[0][i] = matrix[0][i-1]&&(s1.charAt(i-1)==s3.charAt(i-1));
}
for (int i = 1; i < matrix.length; i++){
matrix[i][0] = matrix[i-1][0]&&(s2.charAt(i-1)==s3.charAt(i-1));
}
for (int i = 1; i < matrix.length; i++){
for (int j = 1; j < matrix[0].length; j++){
matrix[i][j] = (matrix[i-1][j]&&(s2.charAt(i-1)==s3.charAt(i+j-1)))
|| (matrix[i][j-1]&&(s1.charAt(j-1)==s3.charAt(i+j-1)));
}
}
return matrix[s2.length()][s1.length()];
}
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
int m = s1.length(), n = s2.length();
if(m+n != c3.length) return false;
return dfs(c1,c2,c3,0,0,0, new boolean[m+1][n+1]);
}
// 使用invalid可以避免boolean初始化的false和結(jié)果false的混淆。
public boolean dfs(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] invalid){
if(invalid[i][j]) return false;
if(k == c3.length) return true;
boolean valid =
i < c1.length && c1[i] == c3[k] && dfs(c1,c2,c3,i+1,j,k+1, invalid) ||
j < c2.length && c2[j] == c3[k] && dfs(c1,c2,c3,i,j+1,k+1, invalid);
if(!valid) invalid[i][j] = true;
return valid;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66927.html
摘要：題目要求輸入數(shù)組和判斷是不是由和中的元素交替組成的。思路一乍一看這題可以通過遞歸的方式來求解。而走到和對應(yīng)的中的也是確定的。這里我們利用數(shù)組記錄判斷情況。所以我們可以將的二維數(shù)組簡化為一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)。提高空間的利用率。 題目要求 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2....
97. Interleaving StringDescriptionHintsSubmissionsDiscussSolutionGiven s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example,Given:s1 = aabcc,s2 = dbbca, When s3 = aadbbc...
摘要：注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計(jì)正數(shù)個數(shù)，若超過序列長度的一半，則正指針從開始，反之則負(fù)指針從開始。注意交換函數(shù)的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。 Problem Given an array with positive and negative integers. Re-range it to interleaving with positiv...
摘要：協(xié)議使用簡述是的一種數(shù)據(jù)交換的格式，它獨(dú)立于語言，獨(dú)立于平臺?？梢杂糜趯ο笮蛄性?，序列化協(xié)議也是一種協(xié)議。 protocol buff 協(xié)議使用 github:https://github.com/chengbingh...(https://github.com/chengbingh... 1 簡述 protocol buff 是google 的一種數(shù)據(jù)交換的格式，它獨(dú)立于語言，獨(dú)立...
摘要：集群三步安裝概述本文教你如何用一條命令構(gòu)建高可用集群且不依賴和，也無需。通過內(nèi)核對進(jìn)行負(fù)載均衡，并且?guī)Ы】禉z測。當(dāng)然你也可以把用于一些其它場景，比如代理自己的服務(wù)等 kubernetes集群三步安裝 概述 本文教你如何用一條命令構(gòu)建k8s高可用集群且不依賴haproxy和keepalived，也無需ansible。通過內(nèi)核ipvs對apiserver進(jìn)行負(fù)載均衡，并且?guī)piserve...
閱讀 1013·2019-08-30 15:55
閱讀 3454·2019-08-30 13:10
閱讀 1279·2019-08-29 18:45
閱讀 2356·2019-08-29 16:25
閱讀 2120·2019-08-29 15:13
閱讀 2434·2019-08-29 11:29
閱讀 562·2019-08-26 17:34
閱讀 1499·2019-08-26 13:57
