华为非AI方向笔试真题 7月15号【字符补全】

字符补全(C++/Py/Java/Js/Go)题解

华为笔试真题 7月15号 非AI方向第三题 300分题型

题目内容

给定一个目标字符串TTT和一个源字符串SSS，请你找出需要在SSS中最少插入多少个字符（可以在任意位置插入），才能使得TTT成为SSS的子序列。

注意：

  1. 子序列定义：对于一个字符串UUU，如果字符串VVV可以通过删除UUU中的一些字符（可以删除000个或多个，不改变剩余字符的相对顺序）得到，则称VVV是UUU的子序列。
  • 例如：在 “acbdacbdacbd” 中，“ababab”、“acacac”、“adadad”、“cdcdcd”、"abcdabcdabcd"等都是其子序列。
  • 子序列中的字符在原字符串中不需要连续出现，但必须保持原有的相对顺序。
  • 例如：“ababab” 是 “axbyaxbyaxby” 的子序列，因为 ‘aaa’ 在 ‘bbb’ 之前出现。
  1. 只能插入字符，不能删除或修改现有字符。
  2. 插入的字符必须是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’。这是特殊情况，展示了重复字符的处理。

题解

思路

思路:动态规划

  1. 本题其实可以直接转换为求S T的最长公共子序列，要插入的字母数量就为T.size() - 最大公共子序列长度。
  2. 求最长子序列使用对应模板即可，定义dp[i][j]数组，表示T 前 i 个字符和 S 前 j 个字符*的最长公共子序列长度
  3. 状态转移
    • 字符相同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]);
  4. 最终结果即为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)}