Search Lines with Line Numbers (grep)
Problem
The first line is a search text (it can contain spaces). All other lines are the text of a file. Print every line that contains the search text, ignoring upper and lower case, written as number: line (line numbers start at 1 and count only the file lines). Print no match if no line contains it.
Constraints
- 1 <= lines <= 10^5
Examples
Input
error all fine ERROR: disk
Output
2: ERROR: disk
Solutions
toLowerCase is enough for plain English text. For other languages use a locale-aware comparison (equalsIgnoreCase or Collator in Java), because some letters change length when they are converted. For regular expressions, use the Pattern class.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : Matching lines.
* Approach: Search text, then the file.
* Time : O(total length)
* Space : O(matches)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
// Step 1: The first line is the search text. We compare in lower case to ignore the case.
String pattern = lines[0].toLowerCase();
java.util.List<String> found = new java.util.ArrayList<>();
// Step 2: Check each file line and remember its number (the first file line has number 1).
for (int i = 1; i < lines.length; i++) {
if (lines[i].toLowerCase().contains(pattern)) {
found.add(i + ": " + lines[i]);
}
}
return found.isEmpty() ? new String[] {"no match"} : found.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
all.add(scanner.nextLine());
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why can toLowerCase be wrong for some languages?