面试算法96:字符串交织

2024-01-09 20:41:32

题目

输入3个字符串s1、s2和s3,请判断字符串s3能不能由字符串s1和s2交织而成,即字符串s3的所有字符都是字符串s1或s2中的字符,字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如,字符串"aadbbcbcac"可以由字符串"aabcc"和"dbbca"交织而成。
在这里插入图片描述

分析

每步从字符串s1或s2中选出一个字符交织生成字符串s3中的一个字符,那么交织生成字符串s3中的所有字符需要多个步骤。每步既可能从字符串s1中选择一个字符,也可能从字符串s2中选择一个字符,也就是说,每步可能面临两个选择。完成一件事情需要多个步骤,而且每步都可能面临多个选择,这个问题看起来可以用回溯法解决。
这个问题并没有要求列出所有将字符串s1和s2交织得到字符串s3的方法,而只是判断能否将字符串s1和s2交织得到字符串s3。如果能够将字符串s1和s2交织得到字符串s3,那么将字符串s1和s2交织得到字符串s3的方法的数目大于0。这只是判断问题的解是否存在(即判断解的数目是否大于0),因此这个问题更适合应用动态规划来解决。
可以用函数f(i,j)表示字符串s1的下标从0到i的子字符串(记为s1[0…i],长度为i+1)和字符串s2的下标从0到j的子字符串(记为s2[0…j],长度为j+1)能否交织得到字符串s3的下标从0到i+j+1(记为s3[0…i+j+1],长度为i+j+2)的子字符串。f(m-1,n-1)就是整个问题的解。
当s3[i+j+1]和s1[i]相同时,f(i,j)的值等于f(i-1,j)的值。类似地,当s3[i+j+1]和s2[j]相同时,f(i,j)的值等于f(i,j-1)的值。如果s1[i]和s2[j]都和s3[i+j+1]相同,此时只要f(i-1,j)和f(i,j-1)有一个值为true,那么f(i,j)的值为true。

public class Test {
    public static void main(String[] args) {
        boolean result = isInterleave("aabcc", "dbbca", "aadbbcbcac");
        System.out.println(result);

    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;

        // 列为0,没有取用s2字符串的数字
        for (int i = 0; i < s1.length(); i++) {
            dp[i + 1][0] = s1.charAt(i) == s3.charAt(i) && dp[i][0];
        }

        // 行为0,没有取用s1字符串的数字
        for (int j = 0; j < s2.length(); j++) {
            dp[0][j + 1] = s2.charAt(j) == s3.charAt(j) && dp[0][j];
        }

        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                char ch1 = s1.charAt(i);
                char ch2 = s2.charAt(j);
                char ch3 = s3.charAt(i + j + 1);
                // 注意是dp[i + 1][j + 1]
                dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1]) || (ch2 == ch3 && dp[i + 1][j]);
            }
        }

        return dp[s1.length()][s2.length()];
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135412977
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。