做网站费用是什么,信用网站建设意见,大学有吗网站建设,中企动力企业z云邮登陆扰乱字符串
难度#xff1a;困难
题目描述
使用下面描述的算法可以扰乱字符串 s 得到字符串 t #xff1a;
如果字符串的长度为 1 #xff0c;算法停止如果字符串的长度 1 #xff0c;执行下述步骤#xff1a; 在一个随机下标处将字符串分割成两个非空的子字符串…扰乱字符串
难度困难
题目描述
使用下面描述的算法可以扰乱字符串 s 得到字符串 t
如果字符串的长度为 1 算法停止如果字符串的长度 1 执行下述步骤 在一个随机下标处将字符串分割成两个非空的子字符串。即如果已知字符串 s 则可以将其分成两个子字符串 x 和 y 且满足 s x y 。随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即在执行这一步骤之后s 可能是 s x y 或者 s y x 。在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2判断 s2 是否是 s1 的扰乱字符串。如果是返回 true 否则返回 false 。
示例1
输入 s1 “great”, s2 “rgeat” 输出 true
示例2
输入 s1 “abcde”, s2 “caebd” 输出 false
示例3
输入 s1 “a”, s2 “a” 输出 true
题解
直接使用动态规划来解题原始的递归方法中存在大量的重复操作从而使时间复杂度大幅提高这时可以使用一个三维数组dp[i][j][k]来记录i表示s1起始位置j表示s2起始位置k表示当前字符串的长度 转移方程如下 dp[i,j,k] (dp[i,j,m] dp[im,jm,k-m]) || (dp[i,jk-m,m] dp[im,j,k-m]) 其中m的取值范围是[1,k)。这表示切割位置可以在1到k之间选择。
想法代码
using System;
using System.Net.Http.Headers;class Solution
{ListListstring strings new ListListstring();public static void Main(string[] args){string s1 great;string s2 rgeat;Solution solution new Solution();bool ans solution.IsScramble(s1, s2);Console.WriteLine(ans);}public bool IsScramble(string s1, string s2){if (s1.Equals(s2)){return true;}int length s1.Length;int[,,] dp new int[length, length, length 1];for (int k 1; k length; k){for (int i 0; i length - k; i){for (int j 0; j length - k; j){if (k 1){dp[i, j, k] s1[i] s2[j] ? 1 : 0;continue;}for (int m 1; m k; m){if ((dp[i, j, m] 1 dp[i m, j m, k - m] 1) || (dp[i, j k - m, m] 1 dp[i m, j, k - m] 1)){dp[i, j, k] 1;break;}}}}}return dp[0, 0, length] 1;}
}
