这是一个创建于 1867 天前的主题，其中的信息可能已经有所发展或是发生改变。
将给定的字符串任意划分成两个非空的部分，组成树的两个左右子结点．子树可以绕根结点变换，最后叶子结点组成一个新的字符串． 比如："abcd"的可以这样划分，然后进行变换
abcd
/ \
a bcd
/ \
b cd
/\
c d
abcd
/ \
ab cd
/\ /\
a b c d
"abcd"可以变换得到"bdca"，则称这两个字符串为相似字符串． "abcd"不能通过变换得到"bdac"．这两个字符串不能称为相似字符串．
有什么思路能够通过函数判断两个字符串是否为相似字符串吗
abcd
/ \
a bcd
/ \
b cd
/\
c d
abcd
/ \
ab cd
/\ /\
a b c d
"abcd"可以变换得到"bdca"，则称这两个字符串为相似字符串． "abcd"不能通过变换得到"bdac"．这两个字符串不能称为相似字符串．
有什么思路能够通过函数判断两个字符串是否为相似字符串吗
 |
1
delectate 2019-10-15 11:52:50 +08:00
分词——求交集——算 cos 值。
|
 |
2
yyh325 OP 如果转化成树，只判断相似，比较简单．但是字符串转化为树，有多种划分方法，不知道怎么样转化成树了
|
 |
3
binux 2019-10-15 12:35:32 +08:00
很简单，你看从结果能不能转换成原字符串就可以了
然后你找到 a 的位置，以它左边为根交换，把 a 换回第一位。 然后对 a 左右两个子串做同样的操作（即找到原右串 b ；原左串最小的字母左侧为根交换） 直到如果你能还原 abcd 即可 |
|
4
yyh325 OP 比如找到 a 的位置，是将 a 划为左子树，还是划为右子树呢．这两种对应不同的树结构． 这里还是想不清楚
|
 |
5
misaka19000 2019-10-15 14:52:57 +08:00
莱文斯坦距离
|
|
6
binux 2019-10-15 14:58:36 +08:00 via Android
@yyh325 #4 无论从哪个位置划分子树，只要交换了 a 的位置，a 右侧元素永远不可能换到 a 左侧，反之亦然。
因为 a 是第一个元素，如果能还原 a 左侧一定是右子树，右侧一定是左子树。 |
 |
8
momocraft 2019-10-15 15:29:38 +08:00  1
```
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 |
|
9
momocraft 2019-10-15 15:34:58 +08:00
称 X(s) 为满足 is_similar(s, x) 的 x 的集合。如果能定义一个 "单调的" X 上的变换函数也许可以更简单些。
|
Select Language