求助一道算法题的思路．判断两个字符串是否为相似字符串

This topic created in 2414 days ago, the information mentioned may be changed or developed.

将给定的字符串任意划分成两个非空的部分，组成树的两个左右子结点．子树可以绕根结点变换，最后叶子结点组成一个新的字符串．　比如："abcd"的可以这样划分，然后进行变换

abcd
/ \
a bcd
/ \
b cd
/\
c d

abcd
/ \
ab cd
/\ /\
a b c d
"abcd"可以变换得到"bdca"，则称这两个字符串为相似字符串．　"abcd"不能通过变换得到"bdac"．这两个字符串不能称为相似字符串．
有什么思路能够通过函数判断两个字符串是否为相似字符串吗

字符

abcd

变换

串

10 replies • 2019-10-15 15:50:28 +08:00

delectate

Oct 15, 2019

分词——求交集——算 cos 值。

yyh325

Oct 15, 2019

如果转化成树，只判断相似，比较简单．但是字符串转化为树，有多种划分方法，不知道怎么样转化成树了

binux

Oct 15, 2019

很简单，你看从结果能不能转换成原字符串就可以了
然后你找到 a 的位置，以它左边为根交换，把 a 换回第一位。
然后对 a 左右两个子串做同样的操作（即找到原右串 b ；原左串最小的字母左侧为根交换）
直到如果你能还原 abcd 即可

yyh325

Oct 15, 2019

比如找到 a 的位置，是将 a 划为左子树，还是划为右子树呢．这两种对应不同的树结构．　这里还是想不清楚

misaka19000

Oct 15, 2019

莱文斯坦距离

binux

Oct 15, 2019 via Android

@yyh325 #4 无论从哪个位置划分子树，只要交换了 a 的位置，a 右侧元素永远不可能换到 a 左侧，反之亦然。
因为 a 是第一个元素，如果能还原 a 左侧一定是右子树，右侧一定是左子树。

binux

Oct 15, 2019

@binux 对不起，我疏忽了。应该是找一个分界线，左侧所有元素大于右侧。

momocraft

Oct 15, 2019

```
is_similar(s1, s2) :=
false IF s1 和 s2 的字符的 set (multiset) 不同 // 显然
true IF s1 和 s2 不长于 2 // 显然
true IF is_similar(s1 的左半, s2 的左半) && is_similar(s1 的右半, s2 的右半)
true IF is_similar(s1 的左半, s2 的右半) && is_similar(s1 的右半, s2 的左半)
false 其他
```
------------

未优化未支持 multiset (和可能重复字符) 的 POC:

https://gist.github.com/jokester/10f9ee0667774e654b9323c02d363281

momocraft

Oct 15, 2019

称 X(s) 为满足 is_similar(s, x) 的 x 的集合。如果能定义一个 "单调的" X 上的变换函数也许可以更简单些。

yyh325

Oct 15, 2019

@binux 嗯，应该可行，假设第一个串是有序的，找一个分界线，左侧为左子树，右侧为右子树．
楼上的稍微复杂一点，不过也是可行的．　暂时没有想到更简捷的