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

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

  •  
  •   yyh325 · 2019-10-15 11:48:57 +08:00 · 1380 次点击
    这是一个创建于 1626 天前的主题,其中的信息可能已经有所发展或是发生改变。
    将给定的字符串任意划分成两个非空的部分,组成树的两个左右子结点.子树可以绕根结点变换,最后叶子结点组成一个新的字符串. 比如:"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
    delectate
        1
    delectate  
       2019-10-15 11:52:50 +08:00
    分词——求交集——算 cos 值。
    yyh325
        2
    yyh325  
    OP
       2019-10-15 11:53:30 +08:00
    如果转化成树,只判断相似,比较简单.但是字符串转化为树,有多种划分方法,不知道怎么样转化成树了
    binux
        3
    binux  
       2019-10-15 12:35:32 +08:00
    很简单,你看从结果能不能转换成原字符串就可以了
    然后你找到 a 的位置,以它左边为根交换,把 a 换回第一位。
    然后对 a 左右两个子串做同样的操作(即找到原右串 b ;原左串最小的字母左侧为根交换)
    直到如果你能还原 abcd 即可
    yyh325
        4
    yyh325  
    OP
       2019-10-15 14:50:28 +08:00
    比如找到 a 的位置,是将 a 划为左子树,还是划为右子树呢.这两种对应不同的树结构. 这里还是想不清楚
    misaka19000
        5
    misaka19000  
       2019-10-15 14:52:57 +08:00
    莱文斯坦距离
    binux
        6
    binux  
       2019-10-15 14:58:36 +08:00 via Android
    @yyh325 #4 无论从哪个位置划分子树,只要交换了 a 的位置,a 右侧元素永远不可能换到 a 左侧,反之亦然。
    因为 a 是第一个元素,如果能还原 a 左侧一定是右子树,右侧一定是左子树。
    binux
        7
    binux  
       2019-10-15 15:06:34 +08:00   ❤️ 1
    @binux 对不起,我疏忽了。应该是找一个分界线,左侧所有元素大于右侧。
    momocraft
        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
    momocraft
        9
    momocraft  
       2019-10-15 15:34:58 +08:00
    称 X(s) 为满足 is_similar(s, x) 的 x 的集合。如果能定义一个 "单调的" X 上的变换函数也许可以更简单些。
    yyh325
        10
    yyh325  
    OP
       2019-10-15 15:50:28 +08:00
    @binux 嗯,应该可行,假设第一个串是有序的,找一个分界线,左侧为左子树,右侧为右子树.
    楼上的稍微复杂一点,不过也是可行的. 暂时没有想到更简捷的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   950 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 21:37 · PVG 05:37 · LAX 14:37 · JFK 17:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.