java - 查找表达式在字符串中连续和非连续出现的次数

Question

我通过电话进行了编码面试，并被问到这个问题:

Given a String (for example):

"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"

和一个表达式(例如):

"a+b+c-"

哪里:

+: means the char before it is repeated 2 times

-: means the char before it is repeated 4 times

求给定表达式在字符串中出现的操作数非连续和连续出现的次数。

上面的表达式出现了4次:

1) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^       ^^       ^^^^                    
        aa       bb       cccc
2) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^       ^^                               ^^^^
        aa       bb                               cccc

3) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^                                ^^      ^^^^
        aa                                bb      cccc

4) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
                                       ^^ ^^      ^^^^
                                       aa bb      cccc

我不知道该怎么做。我开始使用带有大量索引标记的迭代暴力方法，但意识到在中途编写代码会有多么困惑和困难:

import java.util.*;

public class Main {

    public static int count(String expression, String input) {
        int count = 0;
        ArrayList<char[]> list = new ArrayList<char[]>();

        // Create an ArrayList of chars to iterate through the expression and match to string
        for(int i = 1; i<expression.length(); i=i+2) {
            StringBuilder exp = new StringBuilder();
            char curr = expression.charAt(i-1);
            if(expression.charAt(i) == '+') {
                exp.append(curr).append(curr);
                list.add(exp.toString().toCharArray());
            }
            else { // character is '-'
                exp.append(curr).append(curr).append(curr).append(curr);
                list.add(exp.toString().toCharArray());
            }
        }

        char[] inputArray = input.toCharArray();
        int i = 0; // outside pointer
        int j = 0; // inside pointer
        while(i <= inputArray.length) {
            while(j <= inputArray.length) {
                for(int k = 0; k< list.size(); k++) {
                    /* loop through 
                     * all possible combinations in array list
                     * with multiple loops
                     */
                }
                j++;
            }
            i++;
            j=i;
        }
        return count;
    }

    public static void main(String[] args) {
        String expression = "a+b+c-";
        String input = "aaksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
        System.out.println("The expression occurs: "+count(expression, input)+" times");
    }
}

在花了很多时间反复地做这件事之后，他提到了递归，但我仍然看不出递归地做这件事的明确方法，我也无法解决这个问题。我正在尝试在面试后解决它，但我仍然不确定如何解决这个问题。我应该如何解决这个问题？解决方案是否显而易见？我认为这对于编码电话面试来说是一个非常难的问题。

Answer 1

需要O(m) 空间 并在O(n*m) 中运行的非递归算法，其中 m 是查询中的标记数:

@Test
public void subequences() {

    String input = "aabbccaacccccbbd";
    String query = "a+b+";

    // here to store tokens of a query: e.g. {a, +}, {b, +}
    char[][] q = new char[query.length() / 2][];

    // here to store counts of subsequences ending by j-th token found so far
    int[] c =  new int[query.length() / 2];   // main
    int[] cc = new int[query.length() / 2];   // aux        

    // tokenize
    for (int i = 0; i < query.length(); i += 2)
        q[i / 2] = new char[] {query.charAt(i), query.charAt(i + 1)};

    // init
    char[] sub2 = {0, 0};        // accumulator capturing last 2 chars
    char[] sub4 = {0, 0, 0, 0};  // accumulator capturing last 4 chars

    // main loop
    for (int i = 0; i < input.length(); i++) {

        shift(sub2, input.charAt(i));
        shift(sub4, input.charAt(i));

        boolean all2 = sub2[1] != 0 && sub2[0] == sub2[1];  // true if all sub2 chars are same
        boolean all4 = sub4[3] != 0 && sub4[0] == sub4[1]   // true if all sub4 chars are same
              && sub4[0] == sub4[2] && sub4[0] == sub4[3];

        // iterate tokens
        for (int j = 0; j < c.length; j++) {

            if (all2 && q[j][1] == '+' && q[j][0] == sub2[0]) // found match for "+" token
                cc[j] = j == 0             // filling up aux array
                      ? c[j] + 1           // first token, increment counter by 1
                      : c[j] + c[j - 1];   // add value of preceding token counter

            if (all4 && q[j][1] == '-' && q[j][0] == sub4[0]) // found match for "-" token
                cc[j] = j == 0 
                      ? c[j] + 1 
                      : c[j] + c[j - 1];
        }
        if (all2) sub2[1] = 0;  // clear, to make "aa" occur in "aaaa" 2, not 3 times
        if (all4) sub4[3] = 0;
        copy(cc, c);            // copy aux array to main 
        }
    }
    System.out.println(c[c.length - 1]);
}


// shifts array 1 char left and puts c at the end
void shift(char[] cc, char c) {
    for (int i = 1; i < cc.length; i++)
        cc[i - 1] = cc[i];
    cc[cc.length - 1] = c;
}

// copies array contents 
void copy(int[] from, int[] to) {
    for (int i = 0; i < from.length; i++)
        to[i] = from[i];
}

主要思想是从输入中一个一个地捕获字符，将它们保存在 2 字符和 4 字符的累加器中，并检查它们是否与查询的某些标记匹配，记住我们有多少匹配项用于子-到目前为止以这些标记结尾的查询。

查询 (a+b+c-) 被拆分为标记 (a+, b+, c-).然后我们在累加器中收集字符并检查它们是否匹配某些标记。如果我们找到第一个标记的匹配项，我们将其计数器加 1。如果我们找到另一个 第 j 个标记的匹配项，我们可以创建尽可能多的额外子序列来匹配 由标记组成的子查询 [0 ...j]，因为对于由标记 [0...j-1] 组成的子查询，它们中的许多现在都存在 ，因为可以将此匹配附加到它们中的每一个。

例如，我们有:

a+ : 3  (3 matches for a+)
b+ : 2  (2 matches for a+b+)
c- : 1  (1 match for a+b+c-) 

cccc 到达时。然后 c- 计数器应该增加 b+ 计数器值，因为到目前为止我们有 2 个 a+b+ 子序列和 cccc 可以附加到它们。