import java.util.*; class Solution { List solution( List> rules, List queries) { // Keep original index for tie-breaking. List order = new ArrayList<>(); for (int i = 0; i < rules.size(); i++) order.add(i); order.sort((a, b) -> { int lenA = rules.get(a).get(0).length(); int lenB = rules.get(b).get(0).length(); if (lenA != lenB) return Integer.compare(lenB, lenA); return Integer.compare(a, b); }); List ans = new ArrayList<>(); for (String query : queries) { String best = null; for (int idx : order) { String pattern = rules.get(idx).get(0); if (match(pattern, query)) { best = rules.get(idx).get(1); break; } } ans.add(best); } return ans; } // Match pattern at exactly index. boolean find(String pattern, String string, int index) { if (pattern == null || pattern.length() > string.length() - index) { return false; } for (int i = 0; i < pattern.length(); i++) { if (pattern.charAt(i) == '.') continue; if (pattern.charAt(i) != string.charAt(index + i)) return false; } return true; } boolean match(String pattern, String query) { String[] parts = pattern.split("\\*", -1); // Match first part. if (!find(parts[0], query, 0)) return false; int left = parts[0].length(); // Match last part. int last = parts.length - 1; if (last == 0) return left == query.length(); String lastPart = parts[last]; int right = query.length() - lastPart.length(); if (right < left || !find(lastPart, query, right)) { return false; } // Search middle parts between left and right. for (int i = 1; i < last; i++) { String temp = parts[i]; if (temp.isEmpty()) continue; boolean found = false; while (left + temp.length() <= right) { if (find(temp, query, left)) { left += temp.length(); found = true; break; } left++; } if (!found) return false; } return true; } }

Quick Overview

Find best-matching binary pattern with wildcards