查找字符串中连续和非连续表达式的次数

Question

我通过电话进行了编码采访,并被问到这个问题:

给定一个String(例如):

"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"

和表达式(例如):

"A + B + C-"

哪里:

+:表示重复2次之前的字符

- :表示在重复4次之前的char

查找给定表达式出现在字符串中的次数,其中操作数不连续且连续地发生.

上面的表达式发生了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-)。然后我们在累加器中收集字符并检查它们是否与某些标记匹配。如果我们找到第一个 token 的匹配，我们将其计数器增加 1。如果我们找到另一个第 j 个 token 的匹配，我们可以创建与由 token [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-counter 应该增加b+counter 值，因为到目前为止我们有 2 个子a+b+序列并且cccc可以附加到它们两个上。