人工智能AI面试题-2.8 交替字符串

2.8 交替字符串 1. 题目描述 给定三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序。例如，当s1 = "aabcc"，s2 = "dbbca"，s3 = "aadbbcbcac"时，输出true；但如果s3 = "accabdbbca"，则输出false。 2. 分析与解法 这道题不能简单地排序，因为一旦排序，就会改变s1或s2中各个字符原始的相对顺序。既然不能排序，我们可以考虑使用动态规划的方法。 定义dp[i][j]代表s3[0...i+j-1]是否由s1[0...i-1]和s2[0...j-1]的字符组成。如果s1当前字符（即s1[i-1]）等于s3当前字符（即s3[i+j-1]），且dp[i-1][j]为真，那么可以取s1当前字符而忽略s2的情况，dp[i][j]返回真；如果s2当前字符等于s3当前字符，并且dp[i][j-1]为真，那么可以取s2而忽略s1的情况，dp[i][j]返回真。其他情况下，dp[i][j]返回假。 参考代码： ```java public boolean IsInterleave(String s1, String s2, String s3) {   int n = s1.length(), m = s2.length(), s = s3.length();       // 如果长度不一致，则s3不可能由s1和s2交错组成   if (n + m != s)     return false;       boolean[][] dp = new boolean[n + 1][m + 1];       // 在初始化边界时，我们认为空串可以由空串组成，因此dp[0][0]赋值为true。   dp[0][0] = true;   for (int i = 0; i < n + 1; i++) {     for (int j = 0; j < m + 1; j++) {       if (dp[i][j] || (i - 1 >= 0 && dp[i - 1][j] == true &&         // 取s1字符         s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (j - 1 >= 0 && dp[i][j - 1] == true &&         // 取s2字符         s2.charAt(j - 1) == s3.charAt(i + j - 1)))         dp[i][j] = true;       else         dp[i][j] = false;     }   }       return dp[n][m]; } ``` 理解本题及上段代码，对真正理解动态规划有一定帮助。 😎