Untitled
unknown
plain_text
3 months ago
2.3 kB
3
Indexable
import java.util.*; public class Solution { public int numMatchingSubseq(String s, String[] words) { // Map to store indices of each character in s Map<Character, List<Integer>> charIndicesMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { charIndicesMap.computeIfAbsent(s.charAt(i), k -> new ArrayList<>()).add(i); } int count = 0; // Check each word in words for (String word : words) { if (isSubsequence(word, charIndicesMap)) { count++; } } return count; } private boolean isSubsequence(String word, Map<Character, List<Integer>> charIndicesMap) { int prevIndex = -1; for (char c : word.toCharArray()) { // If the character does not exist in s if (!charIndicesMap.containsKey(c)) { return false; } // Binary search to find the next valid position List<Integer> indices = charIndicesMap.get(c); int nextIndex = findNextIndex(indices, prevIndex); if (nextIndex == -1) { return false; // No valid position found } prevIndex = nextIndex; } return true; } private int findNextIndex(List<Integer> indices, int prevIndex) { // Binary search for the smallest index greater than prevIndex int low = 0, high = indices.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; if (indices.get(mid) > prevIndex) { high = mid - 1; } else { low = mid + 1; } } return low < indices.size() ? indices.get(low) : -1; } public static void main(String[] args) { Solution solution = new Solution(); // Example 1 String s1 = "abcde"; String[] words1 = {"a", "bb", "acd", "ace"}; System.out.println(solution.numMatchingSubseq(s1, words1)); // Output: 3 // Example 2 String s2 = "dsahjpjauf"; String[] words2 = {"ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"}; System.out.println(solution.numMatchingSubseq(s2, words2)); // Output: 2 } }
Editor is loading...
Leave a Comment