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

快速算法,怎样判断所有 String2 的字母在 String1 里面是否存在

  •  
  •   729334218 · 2014-09-21 10:03:38 +08:00 · 4156 次点击
    这是一个创建于 3701 天前的主题,其中的信息可能已经有所发展或是发生改变。
    18 条回复    2014-09-23 07:26:14 +08:00
    WeberXie
        1
    WeberXie  
       2014-09-21 10:04:30 +08:00
    大众点评的测评吧,用简单hash啊,我都做完咯
    729334218
        2
    729334218  
    OP
       2014-09-21 10:07:01 +08:00
    麻烦能说一下吗,谢谢啦
    andrewhxism
        3
    andrewhxism  
       2014-09-21 10:26:28 +08:00 via iPad
    Kmp
    Ultratude
        4
    Ultratude  
       2014-09-21 10:29:47 +08:00 via iPhone
    看毛片可以。
    phuslu
        5
    phuslu  
       2014-09-21 10:47:52 +08:00
    啊,当年我的实习面试题就是这个。
    http://ideone.com/pHEEiA
    Exin
        6
    Exin  
       2014-09-21 10:59:42 +08:00
    字母是指a-z?
    用两组bool数组,长度26,表示a-z
    在String2里存在的字母对应的bool值为true,其余为false
    对String1同样的操作
    然后对比两组bool

    算法不是很好,如果效率太低请轻喷、求指导
    wy315700
        7
    wy315700  
       2014-09-21 11:07:31 +08:00
    @Exin 都O(n) 了 效率不低了啊
    hit9
        8
    hit9  
       2014-09-21 11:09:34 +08:00
    Kmp
    proudzhu
        9
    proudzhu  
       2014-09-21 11:32:12 +08:00
    以前看到的用位做标志的
    http://ideone.com/BspbkW
    Exin
        10
    Exin  
       2014-09-21 11:45:12 +08:00
    @wy315700 这样啊……我第一次回答算法方面的问题,比较紧张
    xcv58
        11
    xcv58  
       2014-09-21 11:49:40 +08:00 via Smartisan T1
    @wy315700 请教低于 O(n) 的解法。
    jokester
        12
    jokester  
       2014-09-21 12:36:13 +08:00
    怎樣可以低於O(n) ? 把String1和String2都過一遍已經是O(n)了
    xuelang
        13
    xuelang  
       2014-09-21 12:38:47 +08:00
    @andrewhxism 不是string2在string1中出现,是string2中的字母是否在string1出现..
    lu18887
        14
    lu18887  
       2014-09-21 13:54:11 +08:00 via iPad
    kmp
    yhf
        15
    yhf  
       2014-09-21 14:11:37 +08:00
    大众点评的题目吧,话说你这样真的好么...

    我是开了一个长度26的数组,记录每个字母是否出现过。不过应该还有更好的算法,用位运算什么的,应该可以再减少一点空间,没有细想。
    ghostcat
        16
    ghostcat  
       2014-09-21 14:20:53 +08:00
    kmp+1
    daoluan
        17
    daoluan  
       2014-09-21 15:16:01 +08:00
    kmp o(n)
    andrewhxism
        18
    andrewhxism  
       2014-09-23 07:26:14 +08:00 via iPad
    @xuelang 哦,看错了,无脑哈希之。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3552 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 10:29 · PVG 18:29 · LAX 02:29 · JFK 05:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.