找到最长的子串

问题描述 投票：0回答：4

给定一个字符串和单词列表，我想找到最长的子字符串，使其在提供的单词列表中不存在任何单词。

限制：

The length of the string is 1 to 10^5, with no spaces
The size of the words list is 1 to 10, with no spaces, and each word length is in the range of 1 to 10.

示例：

s = "helloworld"
words = ["wor", "rld"]

解决方案：

Valid longest substring: hellowo , here we don't have "wor", "rld" in this substring. 
Result = 7

这是我的代码，对于较小的输入来说效果很好：

int solve(String s, List<String> list) {
    int answer = 0, j=0;
    for(int i = 0 ; i <= s.length(); i++) {
        String sub = s.substring(j, i);
        for(String e : list) {
            if(sub.contains(e)){
                j = j+1;
                sub = s.substring(j, i);
            }
        }
        answer = Math.max(answer, i-j);
    }
    return answer;
}

此代码的时间复杂度是我假设 O(m*n^2)，其中 n 是输入字符串的大小，m 是列表的大小。

如何降低时间复杂度并用更好的方法解决这个问题。

编辑：根据meron解释更新了时间复杂度。

java algorithm time-complexity
4个回答
1
投票

您的复杂性分析是错误的，因为 

substring
和 
contains
不是恒定时间操作，而是取决于所涉及字符串的长度。

假设输入字符串不包含任何搜索词。然后，您将处理长度为 1, 2, 3, ..., n 的子字符串，并对每个子字符串调用 contains 

m
次，总复杂度为 
O(mn^2)
...

要获得实际的

O(mn)
算法，我会这样做：

var answer = 0;
var j = 0;
for (int i = 0; i < s.length; i++) {
    while (endsWith(s, j, i, words) j++;
    answer = Math.max(answer, i - j);
}

哪里

/** @return whether s[begin..end] ends with a word in words */
boolean endsWith(String s, int begin, int end, List<String> words) {
    for (var word : words) {
        if (endsWith(s, begin, end, word)) {
            return true;
        }
    }
}

boolean endsWith(String s, int begin, int end, String word) {
    var offset = end - word.length;
    if (offset < begin) return false;
    for (int i = 0; i < word.length; i++) {
        if (s.charAt(offset + i) != word.charAt(i)) return false;
    }
    return true;
}

（此代码未经测试，您可能需要修复小错误，但总体思路应该是可靠的）

你能分享一下这个解决方案的时间复杂度吗，我仍然认为它是 O(m*n^2)

endsWith
是
O(m)
，最多调用2n次，因为每次调用都会增加
i
或
j
，每个最多增加
n
次。

1
投票

我相信它可以通过使用trie数据结构的O（N * max_word_length）（至少不存在多项式依赖于字数）TC来解决：

public class SO76451768 {

    public int solve(String s, List<String> list) {
        Trie revert = new Trie(true);
        list.forEach(revert::add);

        char[] chars = s.toCharArray();

        int ans = 0;
        int start = 0;
        int end = 1;

        while (end <= chars.length) {
            int r = revert.matchLen(chars, start, end);
            if (r == 0) {
                ans = Math.max(ans, end - start);
                end++;
            } else {
                start = Math.max(start + 1, end - r + 1);
                end = start + 1;
            }
        }


        return ans;
    }


    static class Trie {

        final boolean revert;

        Trie[] children = new Trie[26];

        boolean eow;

        public Trie(boolean revert) {
            this.revert = revert;
        }

        int matchLen(char[] c, int from, int to) {
            Trie child;
            Trie[] arr = children;
            for (int i = 0; i < to - from; i++) {
                child = arr[c[revert ? to - i - 1 : i + from] - 'a'];
                if (child == null) {
                    return 0;
                }
                if (child.eow) {
                    return i + 1;
                }
                arr = child.children;
            }
            return 0;
        }

        void add(String key) {
            Trie child = null;
            Trie[] arr = children;
            char[] chars = key.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[revert ? chars.length - i - 1 : i];
                child = arr[c - 'a'];
                if (child == null) {
                    child = new Trie(revert);
                    arr[c - 'a'] = child;
                }
                arr = child.children;
            }
            child.eow = true;
        }
    }

}
1
投票

第 1 步：将单词存储在前缀树（又名 trie）中

我们可以将单词存储在前缀树（又名特里树）中，如下所示：根节点最多指向 26 个节点，其中一个节点代表要存储的每个单词的第一个字母。然后，每个节点最多指向 26 个后代，每个字母一个，可以遵循从根到当前节点的前缀。

示例：我们要存储 CAT、CAN、COT、ART、ARE

           root
          /    \
         C      A
        / \     |
       A   O    R
      / \  |   / \
     N   T T  E   T

将单词列表放入前缀树中。如果一个单词是另一个单词的扩展（例如 catatonic 与 cat），请省略较长的单词。也就是说，在创建树时，如果一个单词以带有后代的字母结尾，请从树中删除所有后代。如果一个单词超出了叶子，请忽略它。

这一步是O(禁止单词的字母数之和)

第2步：查找输入字符串中禁用单词的起始和结束索引

维护前缀树中字母的引用/指针的链接列表，最初为空。我将在下面调用这些指针。

首先举个例子：假设输入字符串是CART，禁止的单词是上面的CAN、CAT、COT、ARE、ART。

parse C: create a new pointer to the 'C' child of the root
parse A: create a new pointer to the 'A' child of the root
         update the 'C' pointer to point to its child 'A'
parse R: we don't create a new pointer since no banned word starts with 'R'
         delete the pointer to the 'A' that has no 'R' child
         update the pointer to the other 'A' to point to its R child
parse T: we don't create a new pointer since no banned word starts with 'R'
         update the only remaining pointer to point to its 'T' child. Notice that this is a leaf 3 down from the root, so the end of a length 3 banned word. Store the pair of indices for later use.

请注意，每个指针将始终指向当前字母。每一步都有一个指针：

  1. 移动到与新字母匹配的子级
  2. 如果没有子项与新字母匹配则被删除
    3. 如果根有与新字母匹配的子项（即，如果禁止的单词以新字母开头），则创建
解析输入字符串。对于每个字母：

    对于指针列表中的每个指针，要么 1) 如果当前字母不是后代则删除它，或者如果当前字母是后代则指向适当的后代。
    • 如果可能的话，创建一个指向当前字母的指针作为单词的第一个字母。
    • 如果到达单词的末尾，则字符串中的最后几个字符形成禁用单词。字符计数是前缀树中的深度。注意每个单词开始和结束的索引。
这一步的时间复杂度为O((输入字符串的长度) * (平均指针数量))。我不确定您可能同时激活多少个指针。

第3步：找到不包含任何禁用单词的开始和结束索引的最长子字符串

完成此操作后，在线性附加时间内，您可以使用它来查找不包含禁用单词的最长子字符串。

0
投票
String str = "abcabcd"; int length = str.length(); int maxLength = 0; String longSubString = null; for( int i= 0; i < length; i++){ StringBuilder subString = new StringBuilder(); for(int j = i; j < length; j++){ if(subString.indexOf(String.valueOf(str.charAt(j))) != -1){ break; } subString.append(str.charAt(j)); if(subString.length() > maxLength){ longSubString = String.valueOf(subString); maxLength = subString.length(); } } } System.out.println(longSubString); System.out.println("Longest Substring Length:: "+ maxLength);
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.