主页 / 问题 / 1015224
Accepted
J Mas
Asked:2020-08-20 01:38:56 +0000 UTC2020-08-20 01:38:56 +0000 UTC

在 IDEA 中找到合适的表达式

  • 772

有一组像“青苹果”这样的句子，每个句子有 2 到 7 个单词。您需要在其中找到，例如，使用“gra”或“gap”等关键字的“Green Apple”。我怎样才能做到这一点？

java

3 个回答

  1. Best Answer

    在我看来，在这里使用 Trie 会更好。例如，有一个类

    public class TrieNode {
    private HashMap<Character, TrieNode> _children = new HashMap<>();
    private String _payload = null;
}

    它存储当前单词和子节点，其中每个子节点与一个字符相关联。接下来，编写一个为类添加单词的函数

    public void add(String str) {
    add(str, 0);
}

private void add(String str, int ind) {
    if (str.length() == ind) {
        _payload = str;
        return;
    }

    Character c = str.charAt(ind);
    c = Character.toLowerCase(c);

    if (_children.containsKey(c)) _children.get(c).add(str, ind + 1);
    else {
        TrieNode next = new TrieNode();
        _children.put(c, next);
        next.add(str, ind + 1);
    }
}

    花样搜索功能

    public ArrayList<String> retrieve(String filter) {
    ArrayList<String> result = new ArrayList<>();
    retrieve(filter.toLowerCase(), 0, result);
    return result;
}

private void retrieve(String filter, int index, ArrayList<String> result) {
    if (index < filter.length()) {
        Character current = filter.charAt(index);
        for (Character c : _children.keySet()) {
            if (c.equals(current)) _children.get(c).retrieve(filter, index + 1, result);
            else _children.get(c).retrieve(filter, index, result);
        }
    }

    if (index >= filter.length()) {
        if (_payload != null) result.add(_payload);
        for (TrieNode n : _children.values()) n.retrieve(filter, index, result);
    }
}

    如何测试这一切

    public static void main(String[] args) {
    TrieNode root = new TrieNode();
    root.add("Green Apple");
    root.add("Bla bla bla");
    root.add("StackOverflow");

    ShowSearchResultFor(root, "gra");
    ShowSearchResultFor(root, "gap");
    ShowSearchResultFor(root, "sof");
    ShowSearchResultFor(root, "bbb");
    ShowSearchResultFor(root, "a");
}

private static void ShowSearchResultFor(TrieNode root, String filter){
    System.out.println();
    System.out.println("results for: " + filter);
    for(String ret : root.retrieve(filter)){
        System.out.println(ret);
    }
}

    预期控制台输出

    results for: gra
Green Apple

results for: gap
Green Apple

results for: sof
StackOverflow

results for: bbb
Bla bla bla

results for: a
Bla bla bla
StackOverflow
Green Apple
    • 4

  2. 更简洁但可能（未测试）较慢的方法

    private static void ShowSearchResultFor(String[] words, String filter){
    filter = filter.toLowerCase();

    System.out.println();
    System.out.println("results for: " + filter);

    for(String w : words){
        int ind = 0;
        for(Character cw : w.toLowerCase().toCharArray()){
            if (cw.equals(filter.charAt(ind))) ind++;
            if (ind >= filter.length()){
                System.out.println(w);
                break;
            }
        }
    }
}

    如何检查

    public static void main(String[] args) {
    String[] words = new String[3];

    words[0] = "Green Apple";
    words[1] = "Bla bla bla";
    words[2] = "StackOverflow";

    ShowSearchResultFor(words, "gra");
    ShowSearchResultFor(words, "gap");
    ShowSearchResultFor(words, "sof");
    ShowSearchResultFor(words, "bbb");
    ShowSearchResultFor(words, "a");
    ShowSearchResultFor(words, "StackOverflow");
}

    结论

    results for: gra
Green Apple

results for: gap
Green Apple

results for: sof
StackOverflow

results for: bbb
Bla bla bla

results for: a
Green Apple
Bla bla bla
StackOverflow

results for: stackoverflow
StackOverflow
    • 1

  3. 网游，这是用正则表达式最慢的方式

    private static void ShowSearchResultFor(String[] words, String filter){
    filter = filter.toLowerCase();

    System.out.println();
    System.out.println("results for: " + filter);

    StringBuffer buffer = new StringBuffer();
    for(Character c : filter.toCharArray()){
        buffer.append(c);
        buffer.append(".*");
    }

    Pattern p = Pattern.compile(buffer.toString());
    for(String w : words){
        Matcher m = p.matcher(w.toLowerCase());
        if (m.find()) System.out.println(w);
    }
}

    如何检查

    public static void main(String[] args) {
    String[] words = new String[3];

    words[0] = "Green Apple";
    words[1] = "Bla bla bla";
    words[2] = "StackOverflow";

    ShowSearchResultFor(words, "gra");
    ShowSearchResultFor(words, "gap");
    ShowSearchResultFor(words, "sof");
    ShowSearchResultFor(words, "bbb");
    ShowSearchResultFor(words, "a");
    ShowSearchResultFor(words, "StackOverflow");
}

    结论

    results for: gra
Green Apple

results for: gap
Green Apple

results for: sof
StackOverflow

results for: bbb
Bla bla bla

results for: a
Green Apple
Bla bla bla
StackOverflow

results for: stackoverflow
StackOverflow
    • 1

相关问题