p*****2
发帖数: 21240 | 1 做了recursion的，道理不难。想研究一下bottom up的解法。
http://www.mitbbs.com/article_t/JobHunting/32132145.html
可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Length - CommonSuffixLength) // end of C must reside
in CommonSuffix.
LenA = j
LenB = i - LenA
if X[LenA][LenA+LenC] >= LenB // Common substring must be long
enough for B
return true
Not strictly checked for boundaries. But that's the idea. |
g*********e
发帖数: 14401 | 2 第二题不是前一段讨论过吗 貌似搞出个O(n^4)的解法
后来有个人贴了个linear time的解法，我没细看，不知对不对 |
p*****2
发帖数: 21240 | 3
上边是n^3的，还没心情研究呢。你要是看懂了，给我讲讲
【在 g*********e 的大作中提到】
: 第二题不是前一段讨论过吗 貌似搞出个O(n^4)的解法
: 后来有个人贴了个linear time的解法，我没细看，不知对不对
|
S********t
发帖数: 3431 | 4 下次拿这个题来考人
【在 p*****2 的大作中提到】
:
: 上边是n^3的，还没心情研究呢。你要是看懂了，给我讲讲
|
p*****2
发帖数: 21240 | 5
希望不要碰到你。
【在 S********t 的大作中提到】
: 下次拿这个题来考人
|
c*****l
发帖数: 20 | 6 G 的考官，给人留点后路啊
【在 S********t 的大作中提到】
: 下次拿这个题来考人
|
c*****l
发帖数: 20 | 7 既然是 s1 = A B C D 和 s2 = A C B D 的关系
1： 先找到 B C 和 C B
其实应该是 B x C 和 C x B， x 是 the non-leaf node whose two children are
swapped
举个例子，假设 B = b1 b2 b3, C = c1 c2 c4 c4 (bn, cn is a char)
t1 = b1 b2 b3 x c1 c2 c3 c4
<=>
t2 = c1 c2 c3 c4 x b1 b2 b3
2. reverse t2 to t2'
t2' = b3 b2 b1 x c4 c3 c2 c1
3. 比较 t1 和 t2'
对于每个可能的x, （可能不止一个）reverse t2' 的两个 substring
如果 reversed substring 各自和 t1 的对应 substring 相等
(coding 是不需要 reverse, 比较 substring 时， t2' 指针从后走到前就可以了)
那么，s1 s2 是 scrambled string pairs
如果，没有这个 x 存在, s1 s2 are not. |
