Hiệu quả nhận được tập hợp con của chuỗi "startingWith" ra khỏi một tập hợp

Question

Tôi có một số lớn thiết lập các chuỗi và tôi muốn tạo một tính năng tự động đề xuất cho nó.

Giả bộ là ["foo", "fighter"]

Gõ "f" nên trả lại cả hai giá trị, và gõ "fo" chỉ nên trở "foo".

Hiện tại tôi chỉ đang lặp qua tập hợp và ghi lại kết quả bằng cách gọi startsWith, tuy nhiên quá chậm.

Tiêu chuẩn TreeSet với các chức năng tập hợp con của nó sẽ không giúp ích gì nhiều vì nó chỉ thực hiện một cây RB.

Có giải pháp hiệu quả trong API Java hoặc tôi có phải xây dựng triển khai Set của riêng mình không?

---

Edit: thực hiện của tôi trông như thế này, sử dụng Andrey Naumenkos trie datastructures. Thông báo để tăng kích thước mảng nếu bạn muốn sử dụng ký tự ASCII mở rộng. Nếu bạn sử dụng List thay vì Map bạn sẽ nhận được kết quả theo thứ tự được sắp xếp.

public Set<String> getSubset(String s) { 
    result = new HashSet<String>(); 
    getSubset(root, s); 
    return result; 
} 

private void getSubset(TrieNode node, String s) { 
    TrieNode n = node; 
    for (char ch : s.toCharArray()) { 
     if (n.children[ch] != null) { 
      n = n.children[ch]; 
      continue; 
     } 
     return; 
    } 
    getSubsetR(n, s); 
} 

private void getSubsetR(TrieNode node, String s) { 
    for (char ch = 0; ch < node.children.length; ch++) { 
     TrieNode child = node.children[ch]; 
     if (child != null) 
      getSubsetR(child, s + ch); 
    } 
    if (node.leaf) { 
     result.add(s); 
    } 
} 

Answer 1

gì bạn đang tìm kiếm là một tiền tố cấu trúc dữ liệu cây: http://en.wikipedia.org/wiki/Trie

Mã này ở đây sẽ giúp bạn bắt đầu: https://sites.google.com/site/indy256/algo/trie