Search Matching Lines in a Document
Implement an in-memory search service that allows users to find matching lines in a document. The document is provided as a list of lines when the service is created.
A line matches a query when it contains every word from the query as a complete word. The comparison is case-insensitive, and the query words do not need to appear next to each other or in the same order.
Each document line receives a permanent zero-based identifier equal to its original index. Search results must be returned in increasing order of these identifiers.
After receiving search results, a user may delete a line using its identifier. A deleted line must not appear in future searches. Deleting one line must not change the identifiers of the remaining lines.
Class Definition
SearchService(List<String> documentLines)
- Initializes the service with all lines of the document.
- The identifier of
documentLines.get(i) is i.
- Different identifiers may contain identical line text.
Method Signatures
Search Matching Lines
List<String> search(String query)
- Returns every non-deleted line containing all words from
query.
- Each result is formatted as
"lineId,lineText".
- Results are ordered by increasing
lineId.
- Returns an empty list when no active line matches the query.
Delete a Line
boolean deleteLine(int lineId)
- Deletes the active line identified by
lineId.
- Returns
true when the line existed and was successfully deleted.
- Returns
false when lineId is invalid or the line has already been deleted.
Matching Rules
- Words are separated by one or more spaces.
- Matching is case-insensitive.
- Each query word must match a complete word in the document line.
- Extra words in a document line are allowed.
- Repeated words in a query are treated as a single search condition.
Constraints
1 ≤ documentLines.size() ≤ 100,0001 ≤ documentLines.get(i).length() ≤ 1,0001 ≤ query.length() ≤ 1,000- Document lines and queries contain English letters and spaces.
- Document lines and queries contain at least one word.
-1,000,000,000 ≤ lineId ≤ 1,000,000,000
Examples
Example 1
SearchService(documentLines = List.of("Cloud storage provides fast access", "Local storage can also be fast", "Cloud systems are scalable"))
search(query = "fast storage")
Output: List.of("0,Cloud storage provides fast access", "1,Local storage can also be fast")
Both lines contain the complete words fast and storage, so they are returned in increasing identifier order.
Example 2
SearchService(documentLines = List.of("Green parks make cities pleasant", "Cities need reliable public transport", "Public parks need regular care"))
search(query = "cities")
Output: List.of("0,Green parks make cities pleasant", "1,Cities need reliable public transport")
deleteLine(lineId = 0)
Output: true
search(query = "cities")
Output: List.of("1,Cities need reliable public transport")
The line with identifier 0 is excluded because it was deleted.
Example 3
SearchService(documentLines = List.of("Java supports object oriented programming", "Programming requires regular practice"))
search(query = "PRACTICE programming")
Output: List.of("1,Programming requires regular practice")
Matching is case-insensitive, and both query words occur in the second line.
deleteLine(lineId = 1)
Output: true
deleteLine(lineId = 1)
Output: false
The second deletion returns false because the line has already been deleted.