牛牛与字符串1题解

牛牛想知道在一个字符串s中是否有两个不重叠的子串"NB"和"BN"。
例如，在一个字符串中出现一个子串为"NBN"，那么就是有重叠的。
由于字符串可能会很长，所以牛牛无法解决该问题，所以他想请你帮忙，给定一个字符串s，如果有两个不重叠的子串"NB"和"BN"，返回"YES"，反之，返回"NO"。

题解：题目本意实际上就是寻找NB和BN这两个字符串，如果不想让他们有重合的话，那么就贪心寻找，先找到第一个NB或BN的index，然后从这个index开始继续寻找BN或NB的index，然后我们就可以根据这四个index来判断是否有出现不重叠的子串了，判断方式为(a != -1 && b != -1) || (c != -1 && d != -1)，这里的寻求index的方法用的是c++的find函数，事实上这并不能算是最快的方法，但是对于本题的复杂度来说显然已经足够了。

时间复杂度：STL中的string的find算法用的是朴素的O(n*m)时间复杂度 所以这里为O(2n) 如果用KMP的话可以优化到O(2+n)
空间复杂度：O(1)
参考代码：

class Solution {
public:
    /**
     * 给定一个字符串s，如果有两个不重叠的子串"NB"和"BN"，返回"YES"，反之，返回"NO"。
     * @param s string字符串 代表题意中的字符串s
     * @return string字符串
     */
    string solve(string s) {
        // write code here
        int len = s.size();
        if (len <= 3)
            return "NO";
        int a = s.find("NB");
        int b = s.find("BN", a + 2);
        int c = s.find("BN");
        int d = s.find("NB", c + 2);
        if ((a != -1 && b != -1) || (c != -1 && d != -1))
            return "YES";
        return "NO";
    }
};