通过精确执行K个操作（附加到/从字符串S的末尾删除）将字符串S转换为另一个字符串T

Question

我正在试图解决一个问题。但是我缺少一些角落案例。请帮助我。问题陈述是：

您有一个由小写英文字母组成的字符串S。您可以对S执行两种类型的操作：

1. 在字符串的末尾附加一个小写英文字母

给定一个整数k和两个字符串s和t，通过对s执行上述操作中的k来确定是否可以将s转换为t。

如果可能，打印Yes；否则，打印编号。

Examples 
Input           Output

hackerhappy     Yes
hackerrank
9

5 delete operations (h,a,p,p,y) and 4 append operations (r,a,n,k)

aba             Yes
aba
7

4 delete operations (delete on empty = empty) and 3 append operations

我试过这样做（C语言）：

int sl = strlen(s); int tl = strlen(t); int diffi=0;  

int i;
for(i=0;s[i]&&t[i]&&s[i]==t[i];i++); //going till matching
diffi=i;  

((sl-diffi+tl-diffi<=k)||(sl+tl<=k))?printf("Yes"):printf("No");

请帮我解决这个问题。

非常感谢。

Answer 1

这应该适用于所有情况：

int sl = strlen(s); int tl = strlen(t); int diffi=0;  

int i,m;
for(i=0;s[i]&&t[i]&&s[i]==t[i];i++); //going till matching
diffi=i; 
m = sl+tl-2*diffi;

((k>=m&&(k-m)%2==0)||(sl+tl<=k))?printf("Yes"):printf("No");

Answer 2

您可以使用二进制搜索的另一种方法。

取长度较小的字符串，取长度为/2的子字符串（模式）。

1.如果你得到一个匹配项，则对两个字符串进行二进制搜索（按字符），如果匹配项，则在模式中追加长度/4个字符，如果匹配项，则在模式中追加长度/2^n，否则在原始（长度/2的模式）中追加一个字符，然后重试。

2.如果得到长度为/2的图案不匹配，则将图案长度减少到长度/4，如果得到匹配，则追加下一个字符。

现在重复步骤1和2

如果n1 n2

例子：

s1=Hackerhappy
s2=Hackerrank
pattern=Hacker // length = 10 (s2 is smaller and length of s2=10 length/2 =5)
//Do a binary search of the pattern you will get a match by steps 1 and 2
n1 number of mismatched characters is 5 
n2 number of mismatched characters is 4

Now n1+n2<k // its because we will need to do these much operation to make these to equal.
So Yes

Answer 3

您还需要将其余的操作除以2，因为只需添加和删除字母即可浪费这些操作。

所以也许：

//c语言-如果s==t，则strcmp（s， t）返回0。

if(strcmp(s,t))
    ((sl-diffi+tl-diffi<=k && (k-(sl-diffi+tl-diffi))%2==0)||(sl+tl<=k))?printf("Yes"):printf("No");
else 
   if(sl+tl<=k||k%2==0) printf("Yes"); else printf("No");