クロス文字列/キュー
4675 ワード
説明
3つのキューs 1,s 2,s 3を与え,s 3がs 1とs 2で交差しているか否かを判断する.例えば、s 1はaabcc、s 2はdbcaである.s 3がaadbbcbcacの場合、true(s 1を3つの部分に分解する:aa,bc,cがそれぞれs 2対応位置に挿入する)を返します.そうでなければfalseを返します.
入力サンプル
出力サンプル
マイコード
参考/参考(咳咳)
Monster丶Xuのクロス文字列問題、文字列s 3が文字列s 1とs 2をクロスさせたものか否かを判断する
3つのキューs 1,s 2,s 3を与え,s 3がs 1とs 2で交差しているか否かを判断する.例えば、s 1はaabcc、s 2はdbcaである.s 3がaadbbcbcacの場合、true(s 1を3つの部分に分解する:aa,bc,cがそれぞれs 2対応位置に挿入する)を返します.そうでなければfalseを返します.
入力サンプル
aabcc,dbbca,aadbbcbcac
出力サンプル
true
マイコード
private static String solution(String line) {
//
String[] arr1 = line.split(",");
int len1 = arr1[0].length();
int len2 = arr1[1].length();
int len3 = arr1[2].length();
if (len3 != len1 + len2)
return false + "";
if (len1 == 0)
return (arr1[1] == arr1[2]) + "";
if (len2 == 0)
return (arr1[0] == arr1[2]) + "";
int[][] dp = new int[len1 + 1][len2 + 1];
dp[0][0] = 1;
// init the dp array
for (int i = 1; i <= len1; i++) {
if (arr1[0].charAt(i-1) == arr1[2].charAt(i-1))
dp[i][0] = dp[i - 1][0];
}
for (int i = 1; i <= len2; i++) {
if (arr1[1].charAt(i-1) == arr1[2].charAt(i-1))
dp[0][i] = dp[0][i - 1];
}
// dp
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
int t = i + j;
if (arr1[0].charAt(i-1) == arr1[2].charAt(t-1)) {
dp[i][j] = dp[i - 1][j] | dp[i][j];
}
if (arr1[1].charAt(j-1) == arr1[2].charAt(t-1)) {
dp[i][j] = dp[i][j - 1] | dp[i][j];
}
}
}
//
if (dp[len1][len2] == 1)
return true + "";
return false + "";
}
参考/参考(咳咳)
Monster丶Xuのクロス文字列問題、文字列s 3が文字列s 1とs 2をクロスさせたものか否かを判断する