java - 暴力破解 : count number of sub strings in a string array

Question

我应该做的是创建一个算法来计算一段文本中子字符串的数量，其中子字符串可以是字母 B 后跟 C 或 C 后跟 B。我不确定该怎么做，但我试过了，得出了下面的结果。我想知道我是否做对了。

int substrCount(String S[0...n-1]){
    int count = 0;
    for (int i = 0; i<=n-2; i++) {
        for (int j=i+1; j<i+2; j++) {
            if ((S[i] == 'B' && S[j] == 'C' ) || (S[i] == 'C' && S[j] == 'B')) {
                count = count + 1;
            }
        }
    }
}

我暂时忽略它是包含小写字母还是大写字母。我还需要找到我认为是 O(n^(2)) 的算法的复杂性。我这样做正确吗？如果是这样，我可以提高它的效率吗？

Answer 1

这很适合我

static int substrCount( String str) {
    int count=0;
    for (int i=0; i<str.length()-1; i++)
    {
        boolean bc = (str.charAt(i) == 'B' && str.charAt(i+1) == 'C');
        boolean cb = (str.charAt(i) == 'C' && str.charAt(i+1) == 'B');
        if (bc || cb) {
            count++;
        }
    } 
    return count;
}

您只需将字符串中的字符序列循环一次即可获得所需的结果。检查一对字符是否等于“BC”或“CB”，并将一个索引向前移动到字符串的末尾。

输出示例:

"ACBAA" gives result 1
"ABCBA" gives result 2
"BCBCB" gives result 4
"BBBBB" gives result 0