java - 如何确定一个字符串是否是另一个字符串的子序列而不考虑其间的字符？

Question

我正在尝试编写一个代码来告诉我一个字符串是否是另一个字符串的子字符串。要注意的是，中间是否有字符并不重要，唯一重要的字符是 'A'、'T'、'G' 和 'C'。例如:

"TxxAA" is     a subsequence of "CTyyGCACA"
"pln"   is     a subsequence of "oiu"
"TAA"   is NOT a subsequence of "TCCCA" 

目前我正在做

private boolean subSequence(DNASequence other) {

    other.fix();
    boolean valid = false;
    String t = other.toString();
    data = dataFix(data);
    int index = 0;

    for (int i = 0; i < data.length(); i++) {
        for (int j = 0; j < t.length(); j++) {
            if(data.charAt(i) == t.charAt(j)) {                        
                if( j >= index) {
                    valid = true;
                    index = j;
                    t = t.replace(t.charAt(j), '_');
                } else {
                    valid = false;
                }
            }
        }

    }

    if (data == "" || t == "" ) {
        valid = true;
    }
    return valid;
}

private String dataFix(String data) {
    for (int i = 0; i < data.length(); i += 1) {
        char ch = data.charAt(i);
        if (("ATGC".indexOf(ch) < 0))
            data = data.replace(data.charAt(i), ' ');        
    }
    data = data.replaceAll(" ", "").trim();
    return data;
}

fix() 和dataFix() 方法清除除"ATGC" 之外的所有字符。随着代码的迭代，它会将 t 中与 data.charAt(i) 匹配的字符替换为 _不要重新匹配同一个字母(我遇到了那个问题)。

目前，发生的事情是替换函数正在替换字符串中的每个字符，而不仅仅是特定索引处的字符(这是它应该做的)解决这个问题的更好方法是什么？我哪里错了？谢谢你。

Answer 1

要回答第一个问题“解决此问题的更好方法是什么？”，我建议使用正则表达式(或正则表达式)。正则表达式是一种在文本中表达模式的方式。

对于这个您有搜索词的示例:

TxxAA

描述您正在寻找的模式的正则表达式可以是:

T.*A.*A

无需过多赘述，术语 .* 是表示任意数量(零个或多个)任意字符的表达式。所以这个正则表达式描述了一个模式是:T;然后是任何字符；一种;然后是任何字符；然后是A。

你原来的问题变成了“一个序列是否有一个模式为 T.*A.*A 的子序列？”。 Java 内置了一个正则表达式库，您可以使用 Pattern 和 Matcher 对象来回答这个问题。

一些示例代码作为演示:

public class DnaMatcher {

    static boolean isSearchChar(char c) {
        return 'A' == c || 'T' == c || 'G' == c || 'C' == c;
    }

    static Pattern preparePattern(String searchSequence) {
        StringBuilder pattern = new StringBuilder();
        boolean first = false;
        for (char c : searchSequence.toCharArray()) {
            if (isSearchChar(c)) {
                if (first) {
                    first = false;
                } else {
                    pattern.append(".*");
                }
                pattern.append(c);
            }
        }
        return Pattern.compile(pattern.toString());
    }

    static boolean contains(String sequence, String searchSequence) {
        Pattern pattern = preparePattern(searchSequence);
        Matcher matcher = pattern.matcher(sequence);
        return matcher.find();
    }

    public static void main(String...none) throws Exception {
        System.out.println(contains("CTyyGCACA", "TxxAA")); // true
        System.out.println(contains("TCCCA", "TAA")); // false
    }
}

您可以看到 preparePattern 匹配准备了所讨论的正则表达式。