将一个字符串转换为另一个给定的约束

Question

给定两个字符串s1和s2。Len(s2(<len(s1(。

两个字符串都只有"a"one_answers"b"字符。给定2个操作：

• s2=s2+"a">
• s2=转速(s2(+"b">

通过执行以上两个操作，找出s2是否永远等于s1。

我只能想到一个简单的解决方案，在这个解决方案中，我们可以递归地对s2执行上面提到的两个操作，并且每当两个字符串的长度相等时，我们可以检查s2是否=s1。

但天真解的时间复杂度是指数的：(2^len_diff(，其中len_diff是两个字符串长度的差。

有更好的解决方案吗？

Answer 1

向后工作。不是从s2构建s1，而是从s1的末尾剥离字符。通过这种方式，您可以确定要撤消的操作。如果你最终得了s2，你就完了。

Answer 2

因此，假设答案存在，s1的形式为：

(s₂a*(，(a*bs₂a*ba*(，。。。

或形式

(a*s'₂ba*(，(a*ba*s'<2ba*ba*(，。。。

其中s'₂是s₂的相反

---

所以你的问题归结为寻找正则表达式

s₁=[(a*b(_ns2(a*bⁿa*]V[a*(ba*(ⁿs’_2(ba*(n+1]

这是正确的。您可以使用正则表达式库来解析和检查

---

如果必须从头开始编写解析算法，您甚至不必检查*。你只需计算s_{2两侧的b的数量就可以逃脱惩罚}

伪代码类似于

B1 = number of b's in s2 //O(n)
B2 = number of b's in s1 //O(n)
//Locate s2 in s1 and check b_left = b_right and character before s2 is b
b_to_left = 0
for i from 1 to (s1's length - s2's length): //O(n iteration)
if s2.length characters of s1 starting at index i DO NOT match s2: //At worse O(n to check)
if(s1[i] is b) b_to_left++
continue to next i
b_to_right = B1 - B2 - b_to_left
if(b_to_left == b_to_right) :
if(b_to_left == 0)  RETURN TRUE
else if(s[i-1] is b) RETURN TRUE

if(s1[i] is b) b_to_left++

//Similarly run another round and parse for the second type involving reverse of s2
//I'm leaving that out as an exercise for you since you mentioned it's an interview problem 


RETURN FALSE

---

时间：O(n²(

空间：O(1(