leetcode
leetcode 2551 ~ 2600
找出数组中的美丽下标 I

找出数组中的美丽下标 I

难度:

标签:

题目描述

You are given a 0-indexed string s, a string a, a string b, and an integer k.

An index i is beautiful if:

  • 0 <= i <= s.length - a.length
  • s[i..(i + a.length - 1)] == a
  • There exists an index j such that:
    • 0 <= j <= s.length - b.length
    • s[j..(j + b.length - 1)] == b
    • |j - i| <= k

Return the array that contains beautiful indices in sorted order from smallest to largest.

 

Example 1:

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

 

Constraints:

  • 1 <= k <= s.length <= 105
  • 1 <= a.length, b.length <= 10
  • s, a, and b contain only lowercase English letters.

代码结果

运行时间: 70 ms, 内存: 21.3 MB


/*
题目思路:
1. 使用 Java Stream API 处理字符串 s。
2. 找到所有的 a 的出现位置。
3. 找到所有的 b 的出现位置。
4. 对每个 a 的出现位置 i,检查是否存在一个 b 的位置 j 使得 |j - i| <= k。
5. 如果满足条件,将 i 添加到美丽下标列表中。
6. 最后对美丽下标列表进行排序并返回。
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class BeautifulIndexesStream {
    public static List<Integer> findBeautifulIndexes(String s, String a, String b, int k) {
        int aLen = a.length();
        int bLen = b.length();

        List<Integer> aIndexes = IntStream.range(0, s.length() - aLen + 1)
                .filter(i -> s.substring(i, i + aLen).equals(a))
                .boxed()
                .collect(Collectors.toList());

        List<Integer> bIndexes = IntStream.range(0, s.length() - bLen + 1)
                .filter(i -> s.substring(i, i + bLen).equals(b))
                .boxed()
                .collect(Collectors.toList());

        List<Integer> result = aIndexes.stream()
                .filter(i -> bIndexes.stream().anyMatch(j -> Math.abs(j - i) <= k))
                .sorted()
                .collect(Collectors.toList());

        return result;
    }

    public static void main(String[] args) {
        String s = "isawsquirrelnearmysquirrelhouseohmy";
        String a = "my";
        String b = "squirrel";
        int k = 15;
        System.out.println(findBeautifulIndexes(s, a, b, k)); // 输出:[16, 33]
    }
}

解释

方法:

此题解首先使用两个列表分别存储字符串 s 中所有 a 和 b 的出现下标。使用字符串的 find 方法来找到所有出现的下标,存储在 lsta 和 lstb 中。之后,遍历 lsta 中的每一个下标 i,使用两个指针技术(一个指针遍历 lsta,另一个指针遍历 lstb),查找是否存在一个下标 j 在 lstb 中,使得 |j - i| <= k。如果找到这样的 j,则将 i 添加到结果列表中。最后返回结果列表。

时间复杂度:

O(m*n)

空间复杂度:

O(la + lb)

代码细节讲解

🦆
在查找字符串a和b的所有出现位置时,为什么选择使用find方法而不是其他字符串搜索算法如KMP或Boyer-Moore?
在此题解中,选择使用find方法而不是更复杂的字符串搜索算法如KMP或Boyer-Moore,可能是因为find方法在Python标准库中已经实现,易于使用且足够高效。这些高级算法虽然在最坏情况下提供更优的时间复杂度,但实际编程中,直接使用内置的find方法可以减少代码复杂性和实现错误的风险。此外,除非处理的字符串极长或查找操作极为频繁,否则简单的方法往往在实际应用中已足够高效。
🦆
find方法在查找所有出现位置时是如何确保不会遗漏任何一个可能的匹配位置的?
find方法通过从上一个找到的索引后一个位置开始搜索来确保不遗漏任何匹配位置。每次调用find时,都会指定新的起始位置为上一次找到的匹配位置加1。这样,每次搜索都会从上一个匹配的下一个字符开始,直到字符串末尾。这种方法确保了每个匹配都会被依次找到,不会有重叠或遗漏。
🦆
为什么在遍历lsta的每个索引i时,初始化j为1而不是0,lstb中索引0存储的是-1有什么特殊含义吗?
在lstb中索引0存储的是-1用于处理边界情况,确保即使字符串b在字符串s的开头位置就出现时,也能正确处理比较逻辑。将j初始化为1而不是0是因为索引0的值为-1并不代表一个有效的字符索引,而是一个初始的边界值。遍历lsta的每个索引i时,从lstb的1开始,确保比较的是有效的b字符出现的索引。这种做法避免了无效比较,并且有助于减少不必要的计算。

相关问题