字符补全(C/Py/Java/Js/Go)题解华为笔试真题 7月15号 非AI方向第三题 300分题型题目内容给定一个目标字符串TTT和一个源字符串SSS请你找出需要在SSS中最少插入多少个字符可以在任意位置插入才能使得TTT成为SSS的子序列。注意子序列定义对于一个字符串UUU如果字符串VVV可以通过删除UUU中的一些字符可以删除000个或多个不改变剩余字符的相对顺序得到则称VVV是UUU的子序列。例如在 “acbdacbdacbd” 中“ababab”、“acacac”、“adadad”、“cdcdcd”、abcdabcdabcd等都是其子序列。子序列中的字符在原字符串中不需要连续出现但必须保持原有的相对顺序。例如“ababab” 是 “axbyaxbyaxby” 的子序列因为 ‘aaa’ 在 ‘bbb’ 之前出现。只能插入字符不能删除或修改现有字符。插入的字符必须是TTT中有的字符。约束条件:1≤∣S∣,∣T∣≤25001 \le |S|, |T| \le 25001≤∣S∣,∣T∣≤2500SSS和TTT只包含小写字母′a′a′a′~′z′z′z′输入描述第一行输入目标字符串TTT第二行输入源字符串SSS输出描述输出最少需要插入的字符数量样例1输入abc ac输出1说明在 ‘ccc’ 前面插入 ‘bbb’得到 “abcabcabc”所以需要插入111个字符。这是最典型的情况展示了当目标字符串只比源字符串多一个字符时如何处理。样例2输入abc xyz输出3说明源字符串SSS中没有目标字符串TTT的任何字符需要插入 “abcabcabc” 全部333个字符。这是边界情况展示了当两个字符串完全不相交时如何处理。样例3输入aaab ab输出2说明源字符串SSS只有 “ababab”而目标字符串TTT有三个 ‘aaa’ 和一个 ‘bbb’。可以匹配一个 ‘aaa’ 和一个 ‘bbb’但还需要插入两个 ‘aaa’。这是特殊情况展示了重复字符的处理。题解思路思路:动态规划本题其实可以直接转换为求S T的最长公共子序列要插入的字母数量就为T.size() - 最大公共子序列长度。求最长子序列使用对应模板即可定义dp[i][j]数组表示T 前 i 个字符和 S 前 j 个字符*的最长公共子序列长度状态转移字符相同T[i-1] S[j-1], 对应执行dp[i][j] dp[i - 1][j - 1] 1;字符不相同时执行dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);最终结果即为T.size() - dp[n][m], 总体时间复杂度为OnmC#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);string t,s;cint;cins;intnt.size();intms.size();// dp[i][]j T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。vectorvectorintdp(n1,vectorint(m1,0));for(inti1;in;i){for(intj1;jm;j){if(t[i-1]s[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}intansn-dp[n][m];coutans;return0;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringtsc.next();Stringssc.next();intnt.length();intms.length();// dp[i][j]T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。int[][]dpnewint[n1][m1];for(inti1;in;i){for(intj1;jm;j){if(t.charAt(i-1)s.charAt(j-1)){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}}}intansn-dp[n][m];System.out.print(ans);}}pythontinput()sinput()nlen(t)mlen(s)# dp[i][j]T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。dp[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):ift[i-1]s[j-1]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])ansn-dp[n][m]print(ans)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){consttinput[0];constsinput[1];constnt.length;constms.length;// dp[i][j]T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。constdpArray.from({length:n1},()Array(m1).fill(0));for(leti1;in;i){for(letj1;jm;j){if(t[i-1]s[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}}}constansn-dp[n][m];console.log(ans);});Gopackagemainimport(bufiofmtos)funcmax(a,bint)int{ifab{returna}returnb}funcmain(){in:bufio.NewReader(os.Stdin)vart,sstringfmt.Fscan(in,t)fmt.Fscan(in,s)n:len(t)m:len(s)// dp[i][j]T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。dp:make([][]int,n1)fori:0;in;i{dp[i]make([]int,m1)}fori:1;in;i{forj:1;jm;j{ift[i-1]s[j-1]{dp[i][j]dp[i-1][j-1]1}else{dp[i][j]max(dp[i-1][j],dp[i][j-1])}}}ans:n-dp[n][m]fmt.Print(ans)}
