给定三个字符串A、B和C。编写一个函数,检查C是否是A和B的交错。如果C包含A和B的所有字符,并且每个字符串中所有字符的顺序都被保留,则称C为A和B的交错。
例如: - 'hotdog' 是 'hot' 和 'dog' 的交错(简单) - 'superb' 是 'up' 和 'serb' 的交错 - 'heartache' 是 'ear' 和 'ache' 的交错 - 'chat' 是 'hat' 和 'cat' 的交错 - 'cheaters' 不是 'chat' 和 'seer' 的交错,因为虽然它包含每个字符串的所有字母,但来自 'seer' 的字母没有按顺序出现
我在net中找到了一些解决方案,但下面是我的方法,有人能告诉我是否遗漏了什么或者我的算法是否可行吗?谢谢。 我的算法: Traverse through
For the next char in
Same you do for
If after doing the above step if we find
e.g.
例如: - 'hotdog' 是 'hot' 和 'dog' 的交错(简单) - 'superb' 是 'up' 和 'serb' 的交错 - 'heartache' 是 'ear' 和 'ache' 的交错 - 'chat' 是 'hat' 和 'cat' 的交错 - 'cheaters' 不是 'chat' 和 'seer' 的交错,因为虽然它包含每个字符串的所有字母,但来自 'seer' 的字母没有按顺序出现
我在net中找到了一些解决方案,但下面是我的方法,有人能告诉我是否遗漏了什么或者我的算法是否可行吗?谢谢。 我的算法: Traverse through
a
and c
. While traversal we calculate two things first: whether the char is present or not and save the index i.e. f
where the char is found. And as soon as we find the char we should put some special char in that place, so that we will not consider this char further.For the next char in
a
search in the c
from the index where you have found the previous char i.e. f
. if we don't find than return.Same you do for
b
as well.If after doing the above step if we find
false
than repeat for first b
than a
and return the result.e.g.
a = xxy, b = xxz and c = xxzxxxy
因此,真正的即c是a和b的交错字符串。从
a
开始:
- 对于 a 中的每个 x,c = 0xzxxxy(我将 0 视为特殊字符)。
- 对于 a 中的每个 x,从索引 0 开始(因为我们在索引 0 处找到了前一个字符),c = 00zxxxy。
- 对于 a 中的每个 y,c = 00zxxx0。
- 对于 b 中的每个 x,c = 00z0xx0。
- 对于 b 中的每个 x,c = 00z00x0。
- 对于 b 中的每个 z,在我们找到 b 的前一个字符的索引 4 之后,我们找不到 z。
由于以 b 开头返回 false,所以现在我们将以 b 开始。
所以从 b 开始:
- 对于 b 中的每个 x,c = 0xzxxxy。
- 对于 b 中的每个 x,c = 00zxxxy。
- 对于 b 中的每个 z,c = 000xxxy。
- 对于 a 中的每个 x,c = 0000xxy。
- 对于 a 中的每个 x,c = 00000xy。
- 对于 a 中的每个 y,c = 00000x0。