3
\$\begingroup\$

I've just solved this problem and I hope you guys give me any feedback to make my code be better.

Problem: There are N strings. Each string's length is no more than 20 characters. There are also Q queries. For each query, you are given a string, and you need to find out how many times this string occurred previously.

Input Format

The first line contains N, the number of strings. The next N lines each contain a string. The N + 2nd line contains Q, the number of queries. The following Q lines each contain a query string.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {        
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String[] stringArr = new String[n];

        for (int i = 0; i < n; i++){
                stringArr[i] = scan.next();              
            }

        int q = scan.nextInt();
        for (int i = 0; i < q; i++){
                String stringQue = scan.next();

                int occNum = 0;
                for (int j = 0; j < n; j++){
                    if (stringQue.equals(stringArr[j])) occNum++;                                           
                }
             System.out.println(occNum);
        }   
    }
}
\$\endgroup\$
3
\$\begingroup\$
        String[] stringArr = new String[n];

        for (int i = 0; i < n; i++){
                stringArr[i] = scan.next();              
            }

Why use an array? Consider

        Map<String, Integer> inputCounts = new HashMap<>(n);

        for (int i = 0; i < n; i++) {
            String input = scan.next();

            Integer count = inputCounts.get(input);
            if (count == null) {
                count = 0;
            }

            count++;
            inputCounts.put(input, count);
        }

Now you know the count for each input string. So

                String stringQue = scan.next();

                int occNum = 0;
                for (int j = 0; j < n; j++){
                    if (stringQue.equals(stringArr[j])) occNum++;
                }
             System.out.println(occNum);

could become just

                String query = scan.next();

                Integer count = inputCounts.get(query);
                if (count == null) {
                    count = 0;
                }                          

                System.out.println(count);

If the overhead of the hash accesses is less than the overhead of the for loop, this might be faster.

A HashMap converts the string key into a location in the Map. This is more expensive than a numeric array selection but is probably similar to the cost of the equals method.

I think that we can safely say that accessing the HashMap is going to be faster than iterating over every member of the array unless the array is tiny. The larger question is if the cost of building the HashMap is going to be greater than the savings in processing the queries. For a large number of strings and a small number of queries, the cost of building the HashMap can outweigh the savings in processing the queries. That's trivially true if there are zero queries. And may still be true for one query. There is some point where it stops being true. You'd have to benchmark to be sure.

I prefer names like query and count to stringQue and occNum.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your advise. I haven't use hashmap structure before so I dont know the benefits of using it instead array. Is it truly faster? When should I use hashmap instead array. Anyway I will find and read some more informations about this kind of data structure. Thank you once again! \$\endgroup\$ – Cyrus Cobrazure Nov 22 '16 at 3:08
  • \$\begingroup\$ Looping through an array will be slower than just getting a value from a HashMap if the array is large. \$\endgroup\$ – JollyJoker Nov 22 '16 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.