题解 | #牛牛与字符串1#

牛牛与字符串1

http://www.nowcoder.com/practice/4c1c6afc3a494581ab763c008131b3f3

题意

给定字符串，问是否同时存在"BN" 和 "NB",且这两个存在的位置没有重叠

其中字符串长度 $|s|\leq 10^6$

方法

for 套 for （应该会超时但是没有超时）

遍历字符串，如果找到BN, 则在其不重叠的范围内搜索NB，如果搜索到，那么输出"YES"

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，如果有两个不重叠的子串"NB"和"BN"，返回"YES"，反之，返回"NO"。
     * @param s string字符串 代表题意中的字符串s
     * @return string字符串
     */
    string solve(string s) {
        // write code here
        for(int i = 0;i<s.length()-1;i++){
            if(s[i] == 'B' && s[i+1] == 'N'){
                for(int j = 0;j<i-1;j++){
                    if(s[j] == 'N' && s[j+1] == 'B'){
                        return "YES";
                    }
                }
                for(int j = i+2;j<s.length()-1;j++){
                    if(s[j] == 'N' && s[j+1] == 'B'){
                        return "YES";
                    }
                }
            }
        }
        return "NO";
    }
};

复杂度分析

时间复杂度: 我们每次找到BN,就会在其范围外搜索NB,如果搜索到了就结束。说明每一次搜索代价至少为 字符串长度-4(重叠部分), 而如果大量出现BN,则会触发大量的搜索NB, 因此最坏情况为 $O (∣ s ∣^{2})$ , 然而这题目的数据似乎太弱了，又通过了

空间复杂度: 我们只用了下标等常量来记录遍历状态，所以空间复杂度为 $O (1)$

分别枚举

首先如果"BN"和"NB" 的起始坐标必定不同

如果发生重叠, 有两种情况

BN的下标-NB的下标 = 1

下标	i	i+1	i+2	i+3
BN	-	B	N	-
NB	N	B	-	-

NB的下标-BN的下标 = 1

下标	i	i+1	i+2	i+3
BN	-	B	N	-
NB	-	-	N	B

带上绝对值的话就是下标等于1 则重叠。

那么我们找到s中所有的NB出现的位置，和BN出现的位置，再检查它们之间的下标差有没有大于1的（因为不会重叠,所以不可能等于0）即可

代码

class Solution:
    def solve(self , s ):
        NB = []
        BN = []
        for i in range(len(s)-1):
            if s[i:i+2] == 'NB':
                NB.append(i)
            elif s[i:i+2] == 'BN':
                BN.append(i)
        for i in NB:
            for j in BN:
                if abs(i-j) > 1:
                    return "YES"
        return "NO"

复杂度分析

空间复杂度: 我们记录了分别出现的所有下标，所以总空间复杂度和字符串长度一致 , $O (∣ s ∣)$

时间复杂度: 我们遍历了s，所以遍历时间复杂度为 $O (∣ s ∣)$ 。虽然我们最后两个for套for，看起来是 $O (n^{2})$ ，但实际上，任何一个下标最多和2个另一个下标相邻，所以如果NB和BN有一个长度大于2，那么大于2时就会触发return，否则都小于2，所以最后的for套for时间复杂为常数。总时间复杂度为 $O (∣ s ∣)$