Search result returns more than expected objects in flutter

I have a list of Product objects which have a property called productName. For example:

Product(
  ....
  productName: "Red Shirt",
)

Product(
  ....
  productName: "Yellow Scarf",
)

Product(
  ....
  productName: "Trousers",
)

What I want:

1. When some one searches for Red Scarf, I need to show both red pants and yellow scarf.

My current algorithm:

class Search {
  /*
    A hashmap is used to store the products.
    Key: productName
    Value: Product
  */
  final Map<String, Product> _map = Map.fromIterable(
    products,
    key: (product) => product.productName,
  );

  List<Product> search(String search) {
    List<String> searchWords = search.trim().toLowerCase().split(" ");
    List<Product> result = [];
    for (int i = 0; i < searchWords.length; i++) {
      for (int j = 0; j < products.length; j++) {
        if (products[j].productName!.toLowerCase().contains(searchWords[i])) {
          result.add(products[j]);
        }
      }
    }
    return result.toSet().toList();
  }
}

The issue with this algorithm is when I type in Red S, it shows trousers as well since it has S in it.

I need to solve this issue.

And what better algorithms can be used to reduce the time complexity?

N.B: The _map doesn't do anything. I just thought I might need it.

Solution 1: Guillaume Roux

The most optimised way would be to use RegExp, the following code will consider that one of your words must start with one of "search word", for example with Red S it will search for any words starting with red or s:

class Search {
  Set<Product> search(String search) {
    final searchWords = search.trim().split(" ");
    final searchWordsRegExp = searchWords.formatToWordsRegExp();
    return products.where((product) {
      return product.productName.contains(searchWordsRegExp);
    }).toSet();
  }
}

extension FormatToWordsRegExpExtension on Iterable<String> {
  RegExp formatToWordsRegExp({bool caseSensitive = false}) {
    final buffer = StringBuffer();
    for (final word in this) {
      buffer.write(r'^' + word + r'|\b' + word);
    }
    return RegExp(buffer.toString(), caseSensitive: caseSensitive);
  }
}

Use case

void main() {
  final search = Search();
  final words = ['Red S', 'red s', 'red', 'yellow', 'tro'];
  for (final w in words) {
    print('Search for "$w"');
    search.search(w).showData();
    print('--------------------');
  }
}

Output

Search for "Red S"
Red Shirt
Yellow Scarf
--------------------
Search for "red s"
Red Shirt
Yellow Scarf
--------------------
Search for "red"
Red Shirt
--------------------
Search for "yellow"
Yellow Scarf
--------------------
Search for "tro"
Trousers
--------------------

Try the example on DartPad