java - 特定のプレフィックスで始まる文字列

Question

次のコードがあります。

public List<String> function(String pre) {
    List<String> temp = new ArrayList<>();
    for(String str : list) {
        if(str.startsWith(pre)
            temp.add(str);
        if(str.charAt(0) > pre.charAt(0))
            break;
    }
    return temp;
}

この関数は、指定されたプレフィックスで始まるすべての単語を返す必要があります。
コード内の list は、並べ替えられた ArrayList です。このコードはO(n)複雑です。
どうすれば改善できますか？
たとえば、時間内に実行しlog(n)ます。

Answer 1

Question is - can you do it in O(logn) time?
What if half of the elements in list have the desired prefix? You need to add that half of the list to a new list - this is still O(n).

Answer 2

はい、できます

List<String> function(List<String> list, String pre) {
    List<String> temp = new ArrayList<>();
    for(String str : list) {
        if(str.startsWith(pre))
            temp.add(str);
    }
    return temp;
}