首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
宝塔
V2EX  ›  问与答

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

  •  
  •   yyh325 · 35 天前 · 625 次点击
    这是一个创建于 35 天前的主题,其中的信息可能已经有所发展或是发生改变。
    将给定的字符串任意划分成两个非空的部分,组成树的两个左右子结点.子树可以绕根结点变换,最后叶子结点组成一个新的字符串. 比如:"abcd"的可以这样划分,然后进行变换

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

    abcd
    / \
    ab cd
    /\ /\
    a b c d
    "abcd"可以变换得到"bdca",则称这两个字符串为相似字符串. "abcd"不能通过变换得到"bdac".这两个字符串不能称为相似字符串.
    有什么思路能够通过函数判断两个字符串是否为相似字符串吗
    10 回复  |  直到 2019-10-15 15:50:28 +08:00
        1
    delectate   35 天前
    分词——求交集——算 cos 值。
        2
    yyh325   35 天前
    如果转化成树,只判断相似,比较简单.但是字符串转化为树,有多种划分方法,不知道怎么样转化成树了
        3
    binux   35 天前
    很简单,你看从结果能不能转换成原字符串就可以了
    然后你找到 a 的位置,以它左边为根交换,把 a 换回第一位。
    然后对 a 左右两个子串做同样的操作(即找到原右串 b ;原左串最小的字母左侧为根交换)
    直到如果你能还原 abcd 即可
        4
    yyh325   35 天前
    比如找到 a 的位置,是将 a 划为左子树,还是划为右子树呢.这两种对应不同的树结构. 这里还是想不清楚
        5
    misaka19000   35 天前
    莱文斯坦距离
        6
    binux   35 天前 via Android
    @yyh325 #4 无论从哪个位置划分子树,只要交换了 a 的位置,a 右侧元素永远不可能换到 a 左侧,反之亦然。
    因为 a 是第一个元素,如果能还原 a 左侧一定是右子树,右侧一定是左子树。
        7
    binux   35 天前   ♥ 1
    @binux 对不起,我疏忽了。应该是找一个分界线,左侧所有元素大于右侧。
        8
    momocraft   35 天前   ♥ 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:

        9
    momocraft   35 天前
    称 X(s) 为满足 is_similar(s, x) 的 x 的集合。如果能定义一个 "单调的" X 上的变换函数也许可以更简单些。
        10
    yyh325   35 天前
    @binux 嗯,应该可行,假设第一个串是有序的,找一个分界线,左侧为左子树,右侧为右子树.
    楼上的稍微复杂一点,不过也是可行的. 暂时没有想到更简捷的
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1047 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 22:49 · PVG 06:49 · LAX 14:49 · JFK 17:49
    ♥ Do have faith in what you're doing.