0

问题的文本是这样说的：在给定的字符串中找到最长的子字符串，该字符串由具有 2 个或更多字母的单词组成（这些单词必须是子字符串中的邻居（一个接一个））。约束：运行时间必须低于O(n^2)；

另一个限制是程序必须有一个方法来比较 2 个单词并判断它们是否有 2 个或更多的共同字母。此函数必须在 O(n) 时间内运行。

我认为在该方法中实现 O(n) 时间的唯一方法是使用 Hashtables（您将看到尝试实现此目的的方法的名称是“find”）。这是我对问题的实现： 

public class Subiectul1 {
    String str1;

    Subiectul1(String str1){
        this.str1 = str1;
    }

    public boolean find(String str1, String str2){
        Hashtable<String,Integer> hash = new Hashtable<String,Integer>();
        int count = 0;

        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        for(int i = 0; i < str1.length(); i++){
            hash.put(String.valueOf(str1.charAt(i)), 1);
        }

        for(int i = 0; i < str2.length(); i++){
            if(hash.containsKey(String.valueOf(str2.charAt(i)))) {
                count++; 
                hash.remove(String.valueOf(str2.charAt(i)));
            }
        }

        if(count >= 2) return true;

        return false;
    }

    public void solve(){
        String[] a_str1 = str1.split(" ");
        int n = a_str1.length;
        int[] lmax = new int[n];
        int[] succ = new int[n];
        int max = 0;
        int pmax = -1;

        lmax[n - 1] = 1;
        succ[n - 1] = -1;

        for(int i = n - 2; i >= 0; i--){
            max = 0;
            pmax = -1;
            for(int j = i + 1; j < n; j++)
                if(find(a_str1[i],a_str1[j]) && (max < lmax[j])){
                    max = lmax[j];
                    pmax = j;
                }

            lmax[i] = max + 1;
            succ[i] = pmax;
        }

        pmax = 0;
        max = lmax[0];

        for(int i = 1; i < n; i++)
            if(lmax[i] > max ) {
                pmax = i;
                max = lmax[pmax];
            }

        int i = pmax;
        while(i != -1){
            System.out.print(a_str1[i] + " ");
            i = succ[i];
        }

    }
}

我想知道是否有人有更好的想法，因为这是我能想到的最好的。

4

0 回答 0