python - 在字符串中找到左半部分的计数(符号)=右半部分的计数(符号)的索引？

Question

给定一个字符串，例如 s="##$$$#"，我如何找到索引之前的“#”符号数等于“”数的索引$"符号在索引之后？

示例:如果 s="##$$$#"，则输出将为 2。

解释:在索引 2 之前我们有 2 个“#”符号，在索引 2 之后我们有 2 个“$”符号

我尝试先找到中间索引，然后计算两边的符号(# 和 $)，如果它们相等，则打印中间索引，否则增加中间索引并以相同的方式进行。但我无法正确理解逻辑。

Answer 1

一种方法是:

At any given index 'i' ,
Count_Pound[i] = Count_Pound[i-1] + 1 if charAt(i-1) is '#' 
               = Count_Pound[i-1] if charAt(i-1) is '$'
E.g. Count_Pound[0] = 0;
     Count_Pound[1] = 0 + 1 if charAt(0) = '#'
                    = 0 if charAt(0) is '$'

当您反向移动时，类似的方法也适用。

Count_Dollar[j] = Count_Dollar[j+1] + 1 if charAt(j+1) is '$'
                = Count_Dollar[j+1] if charAt(j+1) is '#'
E.g. Count_Dollar[str.length -1] = 0
     Count_Dollar[str.length - 2] = 0 + 1 if charAt(str.length-1) is '$'
                                  = 0 if charAt(str.length-1) is '#'

一旦你在向前和向后遍历后有了这两个数组 - 顺便说一句，你可以在一个循环中构建这两个数组，有两个索引，一个递增，一个递减。然后遍历这些数组并获得最大的(我假设你想要最大的)。

for i : 0 to str.length-1:
    if Count_Pound[i] == Count_Dollar[i] && max_value < Count_Pound[i]
          max_value = Count_Pound[i]
          ans = i

return ans

空间复杂度不错:O(n)，时间复杂度不错:O(n)