首先让我确保我的理解/抽象是正确的。应满足以下两个要求：
- 如果 A 是 B 的子序列，那么 A 中的所有字符都应该出现在 B 中。
- 对于 B 中的那些字符，它们的位置应该按升序排列。
请注意，A 中的 char 可能在 B 中出现多次。
为了解决 1)，可以使用地图/集合。键是字符串 B 中的字符，值无关紧要。为了解决2），我们需要保持每个字符的位置。由于一个字符可能出现不止一次，因此该位置应该是一个集合。
所以结构是这样的：
Map<Character, List<Integer>)
e.g.
abcdefab
a: [0, 6]
b: [1, 7]
c: [2]
d: [3]
e: [4]
f: [5]
一旦我们有了结构，如何知道字符的顺序是否正确，因为它们在 string 中A？如果B是acd，我们应该检查a位置 0（但不是 6）、c位置 2 和d位置 3。
这里的策略是选择在前一个所选位置之后和接近的位置。TreeSet 是此操作的理想选择。
public E higher(E e)
Returns the least element in this set strictly greater than the given element, or null if there is no such element.
运行时复杂度为 O(s * (n1 + n2)*log(m)))。
- s：集合中的字符串数
- n1：字符串中的字符数（B）
- n2：查询字符串中的字符数（A）
- m：字符串 (B) 中的重复项数，例如有 5 个
a。
下面是一些测试数据的实现。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;
public class SubsequenceStr {
public static void main(String[] args) {
String[] testSet = new String[] {
"abcdefgh", //right one
"adcefgh", //has all chars, but not the right order
"bcdefh", //missing one char
"", //empty
"acdh",//exact match
"acd",
"acdehacdeh"
};
List<String> subseqenceStrs = subsequenceStrs(testSet, "acdh");
for (String str : subseqenceStrs) {
System.out.println(str);
}
//duplicates in query
subseqenceStrs = subsequenceStrs(testSet, "aa");
for (String str : subseqenceStrs) {
System.out.println(str);
}
subseqenceStrs = subsequenceStrs(testSet, "aaa");
for (String str : subseqenceStrs) {
System.out.println(str);
}
}
public static List<String> subsequenceStrs(String[] strSet, String q) {
System.out.println("find strings whose subsequence string is " + q);
List<String> results = new ArrayList<String>();
for (String str : strSet) {
char[] chars = str.toCharArray();
Map<Character, TreeSet<Integer>> charPositions = new HashMap<Character, TreeSet<Integer>>();
for (int i = 0; i < chars.length; i++) {
TreeSet<Integer> positions = charPositions.get(chars[i]);
if (positions == null) {
positions = new TreeSet<Integer>();
charPositions.put(chars[i], positions);
}
positions.add(i);
}
char[] qChars = q.toCharArray();
int lowestPosition = -1;
boolean isSubsequence = false;
for (int i = 0; i < qChars.length; i++) {
TreeSet<Integer> positions = charPositions.get(qChars[i]);
if (positions == null || positions.size() == 0) {
break;
} else {
Integer position = positions.higher(lowestPosition);
if (position == null) {
break;
} else {
lowestPosition = position;
if (i == qChars.length - 1) {
isSubsequence = true;
}
}
}
}
if (isSubsequence) {
results.add(str);
}
}
return results;
}
}
输出：
find strings whose subsequence string is acdh
abcdefgh
acdh
acdehacdeh
find strings whose subsequence string is aa
acdehacdeh
find strings whose subsequence string is aaa
和往常一样，我可能完全错了:)
