Android Contacts Search: Using dialpad keys (alphabets combinations/permutations)

I am trying to a build an Android Dialer App (MinSDK 23).

I'd like to implement a contacts search (usually available in default dialer apps and other third party dialer apps) like below:

As I type digits on dial pad e.g. 245

I should be able to search contacts having phone numbers containing '245' as well as their names containing matches for alphabetical combinations of the digits 245, that as per my calculation should be 27 unique combinations.

While I do know it's a permutations problem and I might be able to search by applying OR 'LIKE' filters on Contacts Name, this doesn't seem efficient enough and it will cause more performance issues as I keep typing e.g. 245658.

How do we do this efficiently? Is there any built-in search mechanism for searching android contacts this way or any better custom solution exists?

I can Filter 1500+ Contact in only 0.5 second ,

You can create same as List< String> or you can go with Object like List< Contact> and just change condition

import java.time.Instant;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

class Scratch {
    public static void main(String[] args) {
        List<String> contactList= new ArrayList<String>();
        contactList.add("Jason  Arnold 9875454454");
        contactList.add("Joshua Ferguson 789455482121");
        contactList.add("Sarah  Churchill 78452165982");
        contactList.add("Brandon    Walsh 78452121");
        contactList.add("Justin Cameron 452197821");
        contactList.add("Rebecca    Howard 784521983232");
        contactList.add("Trevor Smith 372753221");
        contactList.add("Heather    Fraser 9884562145");
        contactList.add("Caroline   Peters 6598421");
        contactList.add("Chloe  Lyman");


        HashMap<String, String> hm = new HashMap<String, String>();
        hm.put("2", "[2abc]");
        hm.put("3", "[3def]");
        hm.put("4", "[4ghi]");
        hm.put("5", "[5jkl]");
        hm.put("6", "[6mno]");
        hm.put("7", "[7pqrs]");
        hm.put("8", "[8tuv]");
        hm.put("9", "[9wxyz]");
        hm.put("1", "[1]");
        hm.put("0", "[0]");

        Instant startTime = Instant.now();
        String findContact = "3727"; // todo
        String regEx = "";
        for (int i = 0; i < findContact.length(); i++) {
            regEx = regEx + hm.get(findContact.charAt(i) + "");
        }

        String finalRegEx = "^"+regEx+".*$";
        System.out.println("!_!_" + finalRegEx);

        List<String> ll = contactList.stream().filter(s -> isMatched(s, finalRegEx))
                .collect(Collectors.toList());
                
        for (int i = 0; i < ll.size(); i++) {
            System.out.println("-->: " + ll.get(i));
        }

        Instant current = Instant.now();
        System.out.println("\nFound List size: " + ll.size());
        long milliseconds = (current.toEpochMilli() - startTime.toEpochMilli());
        System.out.println("\nmilliseconds: " + milliseconds);
    }

    private static boolean isMatched(String str, String finalRegEx) {
        String[] arrOfStr = str.split("\\s");
        for (String a : arrOfStr) {
            if (a.toUpperCase().matches(finalRegEx.toUpperCase()))
                return true;
        }
        return false;
    }
}

Result :

1. Trevor Smith 372753221 (as Phonenumber start with 3727)

2. Heather Fraser 9884562145 (as Last name match with 3727 dial pad keys)

Github code here