LeetCodeAnimation

This document provides a solution and explanation for LeetCode problem #642: Design Search Autocomplete System. The goal is to build a system that returns the top 3 most frequent historical sentences that match a user's current input prefix.

Requirements

• Input: A sequence of characters (lowercase letters, spaces, or a special '#' character).
• Ranking Rules:
  1. Sort by frequency (highest first).
  2. If frequencies are equal, sort by ASCII order (lexicographically smaller first).
  3. Return up to 3 sentences.
• Termination: When '#' is input, the current sentence is saved to the history, and the system resets for a new search.

API Interface

• AutocompleteSystem(String[] sentences, int[] times): Constructor that initializes the system with historical sentence data and their respective frequencies.
• List<String> input(char c): Processes the next character input. Returns the top 3 matching sentences or an empty list if no matches exist or if '#' is input.

Use the following logic to determine if a change on the website requires a synchronization to the GitHub repository:

The bitCount algorithm counts the number of set bits in a 32-bit integer using a divide-and-conquer approach with bit manipulation masks. This method is highly efficient as it uses a fixed number of operations regardless of the input value.

Step-by-Step Bit Counting Logic

1. Count bits in pairs: Sum adjacent bits to get the count of 1s in every 2-bit group. i = i - ((i >>> 1) & 0x55555555)

2. Count bits in nibbles (4-bit groups): Sum adjacent 2-bit groups. i = (i & 0x33333333) + ((i >>> 2) & 0x33333333)

3. Count bits in bytes (8-bit groups): Sum adjacent 4-bit groups and mask to prevent overflow into adjacent groups. i = (i + (i >>> 4)) & 0x0f0f0f0f

4. Count bits in 16-bit groups: Sum adjacent 8-bit groups. i = i + (i >>> 8)

5. Count bits in 32-bit groups: Sum adjacent 16-bit groups. i = i + (i >>> 16)

6. Final Mask: Extract the final count. Since a 32-bit integer can have at most 32 bits set, mask with 0x3f (binary 00111111) to clear unnecessary high bits. return i & 0x3f

public static int bitCount(int i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Floyd's Cycle Detection Algorithm is used to determine if a linked list (or any finite state machine/iterative function) contains a cycle and to find the cycle's starting point.

Mathematical Logic

Let $m$ be the distance from the head to the cycle entrance, and $n$ be the length of the cycle.

When the slow pointer (tortoise) and fast pointer (hare) meet at point $M$ inside the cycle:

• The slow pointer has traveled $x$ steps.
• The fast pointer has traveled $f = 2x$ steps.
• Since the fast pointer is in the cycle, it has completed $k$ full laps: $f = x + kn$.
• Substituting $f = 2x$ gives $x = kn$.

To find the entrance $P$: If we place one pointer at the head and keep the other at the meeting point $M$, and move both at the same speed (1 step at a time), they will meet exactly at the entrance $P$ after $m$ steps, because the distance from the head to the entrance is mathematically equivalent to the distance from the meeting point to the entrance (modulo cycle length).

The recommended approach for this problem is using a Trie (Prefix Tree) combined with a Priority Queue.

Implementation Strategy

1. Data Structure: Use a Trie where each TrieNode stores the full string (str) and its frequency (cnt) if it represents the end of a sentence. Each node also contains a map of children nodes.
2. State Tracking: Maintain a curNode pointer to track the current position in the Trie as the user types, and a stn string to build the current search prefix.
3. Input Processing:
   • If c == '#': The current sentence is complete. Insert it into the Trie (incrementing its count), reset curNode to root, and clear the current string.
   • If c is a valid character:
     • Update curNode to the child node corresponding to c.
     • If the child doesn't exist, set curNode to NULL (no matches possible).
     • If it exists, perform a DFS (Depth First Search) starting from curNode to find all possible sentences in the subtree.
4. Ranking: During DFS, collect all valid sentences into a Priority Queue (Max-Heap) configured with a custom comparator to handle the frequency and ASCII tie-breaking rules. Extract the top 3 elements from the queue for the result.

A problem is generally suitable for Dynamic Programming if it possesses these three properties:

1. Optimal Substructure (最优化): The optimal solution to the problem contains optimal solutions to its subproblems.
2. No Post-effect (无后效性): Once a state at a certain stage is determined, it is not affected by future decisions. The future depends only on the current state, not how the current state was reached.
3. Overlapping Subproblems (重叠子问题): Subproblems are not independent; the same subproblem may be encountered multiple times during the calculation.

Standard DP Workflow:

1. Divide into stages: Partition the problem based on time or space characteristics.
2. Define states and state variables: Describe the different conditions at each stage.
3. Determine decisions and transition equations: Define how states evolve based on choices.
4. Find boundary conditions: Establish the starting values (base cases) for the recursion/iteration.
5. Implement the algorithm.