华为非AI方向笔试真题 7月15号【字符补全】
字符补全(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∣≤2500
- SSS和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], 总体时间复杂度为O（nm）
C++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);string t,s;cin>>t;cin>>s;intn=t.size();intm=s.size();// dp[i][]j T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(inti=1;i<=n;i++){for(intj=1;j<=m;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]);}}}intans=n-dp[n][m];cout<<ans;return0;}java
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringt=sc.next();Strings=sc.next();intn=t.length();intm=s.length();// dp[i][j]：T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。int[][]dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;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]);}}}intans=n-dp[n][m];System.out.print(ans);}}python
t=input()s=input()n=len(t)m=len(s)# dp[i][j]：T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。dp=[[0]*(m+1)for_inrange(n+1)]foriinrange(1,n+1):forjinrange(1,m+1):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])ans=n-dp[n][m]print(ans)javascript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{constt=input[0];consts=input[1];constn=t.length;constm=s.length;// dp[i][j]：T 前 i 个字符 和 S 前 j 个字符 的最长公共子序列长度。constdp=Array.from({length:n+1},()=>Array(m+1).fill(0));for(leti=1;i<=n;i++){for(letj=1;j<=m;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]);}}}constans=n-dp[n][m];console.log(ans);});Go
packagemainimport("bufio""fmt""os")funcmax(a,bint)int{ifa>b{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,n+1)fori:=0;i<=n;i++{dp[i]=make([]int,m+1)}fori:=1;i<=n;i++{forj:=1;j<=m;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)}