You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

5013. 字符串的索引对 - Index Pairs of a String

. 2 min read

【字符串匹配】

给出 字符串 text字符串列表 words, 返回所有的索引对 [i, j] 使得在索引对范围内的子字符串 text[i]...text[j](包括 ij)属于字符串列表 words

Example:

示例 1:

输入: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
输出: [[3,7],[9,13],[10,17]]

示例 2:

输入: text = "ababa", words = ["aba","ab"]
输出: [[0,1],[0,2],[2,3],[2,4]]
解释: 
注意,返回的配对可以有交叉,比如,"aba" 既在 [0,2] 中也在 [2,4] 中

提示:

  1. 所有字符串都只包含小写字母。
  2. 保证 words 中的字符串无重复。
  3. 1 <= text.length <= 100
  4. 1 <= words.length <= 20
  5. 1 <= words[i].length <= 50
  6. 按序返回索引对 [i,j](即,按照索引对的第一个索引进行排序,当第一个索引对相同时按照第二个索引对排序)。

Analysis

简单题目,暴力查找即可

!> 需要注意的是返回的结果需要排序

Solution 【字符串匹配】

执行用时 : 6 ms, 在Index Pairs of a String的Java提交中击败了100.00% 的用户

内存消耗 : 36.7 MB, 在Index Pairs of a String的Java提交中击败了100.00% 的用户

class Solution {
    public int[][] indexPairs(String text, String[] words) {
        Stack<int[]> stack = new Stack<>();
        for (String pattern : words) {
            // System.out.println("\n" + text+"\t"+pattern);
            int len = pattern.length();
            int offset = 0;
            int idx = text.indexOf(pattern);
            while(idx != -1) {
                // System.out.print(idx + " ");
                int[] tmp = {idx, idx + len -1};
                stack.push(tmp);
                offset = idx + 1;
                idx = text.indexOf(pattern, offset);
                
            }
        }
        int[][] res = new int[stack.size()][2];
        int i = 0;
        for (int[] tmp : stack) {
            res[i++] = tmp;
        }
        Arrays.sort(res, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] < b[0])
                    return -1;
                else if (a[0] > b[0])
                    return 1;
                else {
                    if (a[1] < b[1])
                        return -1;
                    else if (a[1] > b[1])
                        return 1;
                }
                return 0;
            }
        });
        return res;
    }
}

这里的匹配采用了 String.indexOf() 进行操作,因此复杂度较高

可以优化为采用 KMP 或 Boyer-Moore 等算法进行匹配,使得匹配部分时间复杂度接近 $O(N)$