求最优算法---关于字符串数组的问题

Question

有两个字符串组A，B
求这两字符串数组元素字符序列相同并且长度最长的元素
（即：两数组的交集中长度最长的字符串）

Answer 1

我这边有一个  但肯定不是最优的public String order(String[] a,String[] b){
String s = "";
int m=0,n=0;
for(int i=0;i<a.length;i++){
for(int j=0;j<b.length;j++){
if(a[i].equals(b[j])){
m=a[i].length();
}
if(m>n){
n=m;
s=a[i];
}
}
}
return s;
}

Answer 2

最长公共子序列问题，可以用动态规划法。给你个链接地址：http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/problems/problem_set/LCS/solution.htm

Answer 3

不知道这两个方法符不符合你要求。
一个用 HashSet，一个用 纯数组，都进行了局部优化。
时间复杂度，未知。    public static String g(String[] arg0, String[] arg1) {
        Set<String> set = new HashSet<String>();
        String s = null;
        for (String str : arg0) {
            set.add(str);
        }
        int x = -1;
        for (String str : arg1) {
            if (set.contains(str) && str.length() > x) {
                s = str;
                x = s.length();
            }
        }
        return s;
    }    public static String h(String[] arg0, String[] arg1) {
        Comparator<String> obj = new Comparator<String>() {            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        };
        Arrays.sort(arg0, obj);
        Arrays.sort(arg1, obj);
        int k = -1;
        for (int i = 0; i < arg0.length; i++) {
            int il = arg0[i].length();
            for (int j = k + 1; j < arg1.length; j++) {
                int jl = arg1[j].length();
                if (jl > il) {
                    k = j;
                } else {
                    if (jl < il) {
                        break;
                    }
                    if (arg0[i].equals(arg1[j])) {
                        return arg0[i];
                    }
                }
            }
        }
        return null;
    }

Answer 4

HashSet 是哈希表实现的，无序的结合,表现为检索(contains)的时间复杂度是 o(0) 
abc130314 的
 
    public static String g(String[] arg0, String[] arg1) {
        Set<String> set = new HashSet<String>();
        String s = null;
        for (String str : arg0) {
            set.add(str);
        }
        int x = -1;
        for (String str : arg1) {
            if (set.contains(str) && str.length() > x) {
                s = str;
                x = s.length();
            }
        }
        return s;
    }
看样子是这个了 
这个复杂度是 O（n）－－－－－！！！

Answer 5

LCS问题的时间复杂度本来就是在mn与min{m,n}之间，但是楼主，java的hashset是封装好的，执行是需要代价的，这么重要的数据结构的实现你没有考虑在你的算法时间复杂度里，所以你的算法从根本上说，并不是min{m,n}。

Answer 6

HashSet 是哈希表实现的，无序的结合,表现为检索(contains)的时间复杂度是 o(0) 

Answer 7

确切地说的 HashSet 是哈希表实现的，无序的结合,表现为检索(contains)的时间复杂度是 o(1) 

Answer 8

HashSet实现不需要代价么？打个比喻，自己揉面包水饺再煮跟从超市买速冻水饺煮着吃，都是吃水饺，但是一个水饺本质上是从面粉和菜到水饺。不能因为说是有速冻水饺了，包水饺就不用面粉和菜了？再如java里面的sort，已经封装好了各种排序方法，你调用执行了一下，难道排序的代价就变成1了？

Answer 9

再如java里面的sort里边你去读下源代码
好像小于7个元素 是用的冒泡法  代价是O（n^2）
大于40个好像是快速排序法 这都是由代价的但hash的代价是是很小  是常数级的 
数据结构中都的讲到 
不是说没代价

Answer 10

不好意思，没看仔细，楼主你讨论的不是LCS，问题跟我想的不是一个级别的东西。至于数据结构或者算法，就不敢向楼主你赐教了。再次表示歉意。