时间戳

首页 > 解决方案 > 字符串中交替字符的最长子串

algorithm - 字符串中交替字符的最长子串

问题描述

我一直在解决给定由小写字符组成的字符串的分而治之问题，找到由连续 {consonant, vowel} 组成的最长子字符串及其在字符串上的位置。

例子。

字符串 = "ehbabebaehehehbe"

解决方案=“babeba”位置：3

我尝试了很多东西，我发现了这些问题。

  1. 我不知道在哪里拆分问题，因为我可能会拆分解决方案，并合并子解决方案，解决方案可能会消失
  2. 合并子解决方案时，我不知道是否应该合并它们或选择其中之一，因为我不知道它们是否是连续的

标签： algorithmrecursionsearchdivide-and-conquer

解决方案

我已经给了你一些时间来解决你的问题。我想出了一个算法。这是详细信息。

概念

我们将使用两种方法：

1: int[] maxSubstringOfAlternatingCharacters(String string, int low, int high)

在这种方法中，我们简单地将字符串分成两部分。我们将从中间分割字符串。此方法返回一个形式为 的数组{startIndex, substringLength}。

2: int[] maxCrossingSubstring(String string, int low, int mid, int high)

在这种方法中，我们找到最大长度的子字符串，其中包含 low 和 high 之间的交替字符。此方法返回一个形式为 的数组{startIndex, substringLength}。

算法

方法一：

1:  int[] maxSubstringOfAlternatingCharacters(String string, int low, int high)
2:
3:      if (low == high) return {low, 1}
4:      
5:      mid = (low + high)/2
6:      leftSubstring = maxSubstringOfAlternatingCharacters(string, low, mid)
7:      rightSubstring = maxSubstringOfAlternatingCharacters(string, mid+1, high)
8:      crossingSubstring = maxCrossingSubstring (string, low, mid, high)
9:
10:     if leftSubstring[1] >= rightSubstring[1] and leftSubstring[1] >= crossingSubstring[1]
11:         return leftSubstring
12:     else if rightSubstring[1] >= leftSubstring[1] and rightSubstring[1] >= crossingSubstring[1]
13:         return rightSubstring
14:     else
15:         return crossingSubstring

方法二：

1:  int[] maxCrossingSubstring (String string, int low, int mid, int high)
2:
3:      if char[mid] and char[mid+1] are not alternating characters
4:          return {low, 0};
5:
6:      leftMaxSubstring = 1;
7:      //Loop from mid to low to find leftMaxSubstring of alternating characters*/
8:      rightMaxSubstring = 1;
9:      //Loop from mid+1 to high to find rightMaxSubstring of alternating characters*/
10:     return {mid-leftMaxSubstring+1, leftMaxSubstring+rightMaxSubstring}

时间复杂度

分割步骤需要O(1)时间。组合步骤，即找到最大交叉子串在最坏的O(n)时间n是在哪里high-low+1。

递归关系将是：

T(n) = 2T(n/2) + O(n)

这导致时间复杂度为O(n*logn)。

最后的想法

我没有提供maxCrossingSubstring方法的完整实现。你应该尝试自己做。如果您遇到任何问题，请发表评论，我也会完成它。如果您在理解算法的任何部分时遇到任何困难，请发表评论，我会更新我的答案以帮助您。

我认为可能有一个更快的算法来解决你的问题，它将在O(n). 它将类似于Kadane's algorithm，因此它不会是分而治之算法。

我希望我对你有所帮助。我确实自己实现了这个算法，它对我来说确实适用于许多输入。如果有人发现它有什么问题。做评论。

推荐阅读