字符串分区，使得分区按递增顺序排列

Question

字符串分区，使得分区按递增顺序排列

algorithm

3

给定一串数字，例如 "12335457"。有效的分割是指字符串的一个分割，使得每个段严格大于前一个段。

例如，"12 | 33 | 54 | 57" 是一个有效的分割，而 57 > 54 > 33 > 12。另一个有效的分割可以是 "12 | 335 | 457"。

对于给定的字符串，有多少个有效的分割？该字符串的最大长度可以为 5000。

如果我们使用动态规划，参数为 i 和 j，表示最后一个段来自 i 到 j，则我们可以对剩余部分进行递归处理。

int solve(int i,int j) {
    // memoization need to be added
    int last_length = j - i + 1;
    int ans = 0;
    for(int k = j + last_length ; k < n ; k++) {
        if( segment(j+1,k) > segment(i,j) ) {   // this is possible in O(1) even if segment lengths are equal
                                                // we should do some pre preocessing on the given string
                                                // which can take O(n^2) time
                                                // if segment(j+1,k) length is more than L , then it is trivial
            ans += solve(j+1 , k);
        }
    }
}

但是这种方法需要 O(n^3) 的时间。我们如何将其从 O(n^3) 减少？谢谢。

- Debashish

有任何限制吗？ - Pham Trung

我的意思是时间上有限制。O(n^3) 会超时。给定字符串的长度最大为 5000，其中 n 是字符串的长度。 - Debashish

子字符串可以以 0 开头吗，例如 0047？ - Pham Trung

@PhamTrung 在这个问题中，数字只是正数。 - Debashish

2个回答

1

我们可以使用一个O(n^2)的算法。让f(i, j, s)表示字符串s中以第i个字符结尾、向前延伸j个字符的有效分区数。则有：

f(i, j, s):
  # A segment extending all the way to the start
  if i + 1 == j:
    return 1

  # A one-character segment that's smaller
  # than the preceding character
  if j == 1 and s[i] <= s[i - 1]:
    return 0

  segment = s[i - j + 1...i]

  # Find longest preceding segment in O(1)
  longest = 
    a segment of length j extending back
    from s[i - j] or length (j-1) if the first
    segment was equal or larger than segment

  # Replace 'sum' with O(1) prefix sum calculation
  # since we can record that for each previous i
  # as we increase j
  return sum(f(i - j, k, s) for k = 1 to length(longest))

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

观察：

Let call the min index that segment(j + 1 , index) > segment(i, j) is x, we can see that solve(i, j) = sum( solve(j + 1, k) ) with x <= k < n

so, let call dp[i][j] = sum(solve[i][k]) with j <= k < n, we have our function:

int solve(int i,int j) {
  // memoization need to be added
  int last_length = j - i + 1;
  int ans = 0;
  int index = getMinIndexForSegment(i,j)
  ans = solve(j + 1, index) + solve(i, j + 1);
  return ans;
}

The last problem is how to calculate getMinIndexForSegment? we realise that we can use binary search to quickly find its result.

int  getMinIndexForSegment (int i, int j){
   int st = j + 1;
   int ed = n - 1;
   int res = n;
   while(st <= ed){
      int mid = (st + ed)/2;
      if(segment(i, j) < seg(j + 1, mid)){
         res = mid;
         ed = mid - 1;
      }else{
         st = mid + 1;
      }

   }
   return res;
}

正如OP所提到的，如果数字只包含正数，那么我们只需要比较两个段落 (i , j) 和 (j + 1 , k)，其中 k - j - 1 = j - i。