java - 处理字符串的问题？

Question

比如我现在想处理两个字符串，

String a = "北大再现一个人的毕业照你好哈哦额的了呢";
String b = "北大现百度一个阿里人毕照哈哦腾讯的了呢";

以a为基准，a里面包含的字，如果在b里面也有，就把它提取出来，也就是最后可以得到的字符串应该是"北大现一个人毕业照哈哦的了呢"。
这样各位有什么好的思路，最好算法速率快一点，时间上快，空间上到随意。
如果时间上是在快不起来，也说说思路。

我现在的思路是很蠢的，把字符串分成一个字的N段，然后两个for嵌套，相同就拿出来，实在是太蠢了。

Answer 1

我的想法是先分别排序，但是记住字符串一的原始序列

然后扫描一遍这两个字符串

可理解，不明白的地方直接评论

上面这个方法不好

可以用hash的方法，这样判断a里面的字符是否在b里面就只要O(1)的时间复杂度了

Answer 2

for(char c:a.toCharArray())
            if(b.contains(String.valueOf(c)))
                System.out.print(c);

Answer 3

javascript,只提供一个思路

var a = '北大再现一个人的毕业照你好哈哦额的了呢'
var b = '北大现百度一个阿里人毕照哈哦腾讯的了呢'
a.split('').filter(k=>~b.indexOf(k)).join('')

...]

Answer 4

我想到一个办法，但应该不是最优，就当给题主一个参考吧。

String a = "北大再现一个人的毕业照你好哈哦额的了呢";
String b = "北大现百度一个阿里人毕照哈哦腾讯的了呢";

Set set = new HashSet();
for (int i = 0; i < b.length(); i++) {
    set.add(String.valueOf(b.charAt(i)));
}

StringBuilder result = new StringBuilder();
for (int i = 0; i < a.length(); i++) {
    String str = String.valueOf(a.charAt(i));
    if(set.contains(str)){
        result.append(str);
    }
}

System.out.println(result);

Answer 5

思路很简单：利用hash。

准备一个hash表，先把a遍历一遍，分别以a中的每个字符作为key，这些key对应的value全置为true；然后遍历b，分别以b中的每个字符作为key，发现key对应的value为true，则说明这个字符既在a中又在b中。

Answer 6

这个是常见的最长公共子序列（LCS）问题，时间复杂度是O(N^2),如果想把具体的字符串找出来，记录一个前缀就行，还有偏一点的算法是O（nlgn)。