3個(gè)字符串a(chǎn)，b，c。判斷c是否是a和b的interleave，也就是c中應(yīng)該有a，b中所有字 符，并且c中字符順序和a，b中一樣。比如，
1. a = "ef" b = "gh" c = "egfh" return true
2. a = "ef" b = "gh" c = "ehgf" return false
分析：
這個(gè)題目中，并沒(méi)有說(shuō)明a和b中是否有相同的字符，這個(gè)直接影響了最終的解法。所以，大家在面試的過(guò)程中，要和面試官進(jìn)行交互，弄清楚之后再動(dòng)手。a和b中不含有相同字符的情況很簡(jiǎn)單，這里略去。下面給出a和b中包含相同字符的動(dòng)態(tài)規(guī)劃的解法。
1 public class Solution {
2 public boolean isInterleaved(String a, String b, String c) {
3 int lengthA = a.length();
4 int lengthB = b.length();
5 int lengthC = c.length();
6 if (lengthA + lengthB != lengthC)
7 return false;
8 boolean[][] map = new boolean[lengthB + 1][lengthA + 1];
9 map[0][0] = true;
10 for (int m = 1; m < lengthA; m++) {
11 map[0][m] = (a.charAt(m - 1) == c.charAt(m - 1) && map[0][m - 1]);
12 }
13 for (int n = 1; n < lengthB; n++) {
14 map[n][0] = (b.charAt(n - 1) == c.charAt(n - 1) && map[n - 1][0]);
15 }
16 for (int i = 1; i <= lengthB; i++) {
17 for (int j = 1; j <= lengthA; j++) {
18 map[i][j] = (c.charAt(i + j - 1) == b.charAt(i - 1) && map[i - 1][j])
19 || (c.charAt(i + j - 1) == a.charAt(j - 1) && map[i][j - 1]);
20 }
21 }
22 return map[lengthB][lengthA];
23 }
24 }