acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 本道题个人解法—通过字符串的删除判断

    算法基本思路: 从两个字符串中删除可以匹配的字符,然后检查剩余字符数 具体步骤: 1.遍历字符串a 2.对于a中的每个字符u,在b中查找是否存在 3.如果存在,删除a中的这个字符和b中对应位置的字符 4.如果不存在,继续检查a的下一个字符 5.处理完后,如果两个字符串剩下的字符数都≤1,则相似 为什么这个算法有正确性: 虽然看起来简单,但实际上是基于编辑距离的变形: 1.完全相同的字符串: 所有字符都能匹配删除,最终a和b都为空,长度都≤1,输出similar 2.修改一个字符: 只有一个字符不同,其他都能匹配删除,最终各剩1个字符,输出similar 3.插入/删除一个字符: 短串的所有字符都能在长串中找到,最终短串为空,长串剩1个字符,输出similar 4.不相似的情况: 会有至少2个字符无法匹配,最终某个字符串长度≥2,输出not similar 时间复杂度: 最坏情况:O(n×m),其中n、m为字符串长度 本题限制字符串长度≤50,完全在可接受范围内 代码如下: 如果不清楚find()+erase()函数的标准代码的话可以到我的主页中的U116621看

    userId_undefined
    WERT
    3月全勤卷王时空双修者快乐小狗俄罗斯套娃大师
    44阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页