Given a string S and Q query strings(q1,q2,...), check for each query string whether or not it is sub-sequence of S

Question

Here is my approach. Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

import java.io.InputStreamReader;
import java.util.Scanner;

public class Query {

public static void main(String[] args) {

    Scanner scanner = new Scanner(new InputStreamReader(System.in));
    String str=scanner.next();
    int n=scanner.nextInt();
    while(n-->0){
        String sub=scanner.next();
        if(isSub(str,sub))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

static boolean isSub(String str, String sub){
    int j=0;
    int x=str.length();
    int y=sub.length();
    for(int i=0;i<x && j<y;i++){
        if(str.charAt(i)==sub.charAt(j)) j++;
    }
    return (j==y);
}
}

Please critique my code and also suggest me how to increase efficiency of this code.

Answer 1

Formatting

Your code is hard to read when formatted like this:

static boolean isSub(String str, String sub){
    int j=0;
    int x=str.length();
    int y=sub.length();
    for(int i=0;i<x && j<y;i++){
        if(str.charAt(i)==sub.charAt(j)) j++;
    }
    return (j==y);
}

Any IDE can automatically reformat this nicely as:

static boolean isSub(String str, String sub) {
    int j = 0;
    int x = str.length();
    int y = sub.length();
    for (int i = 0; i < x && j < y; i++) {
        if (str.charAt(i) == sub.charAt(j)) {
            j++;
        }
    }
    return (j == y);
}

Naming

The single-letter variables x and y are not easy to follow. Consider this alternative:

static boolean isSub(String source, String sub) {
    int subIndex = 0;
    int sourceLen = source.length();
    int subLen = sub.length();
    for (int i = 0; i < sourceLen && subIndex < subLen; i++) {
        if (source.charAt(i) == sub.charAt(subIndex)) {
            subIndex++;
        }
    }
    return subIndex == subLen;
}

Efficiency

A minor optimization is to first check if the source string is longer than the sub:

static boolean isSub(String source, String sub) {
    int sourceLen = source.length();
    int subLen = sub.length();
    if (sourceLen < subLen) {
        return false;
    }

    int subIndex = 0;
    for (int i = 0; i < sourceLen && subIndex < subLen; i++) {
        if (source.charAt(i) == sub.charAt(subIndex)) {
            subIndex++;
        }
    }
    return subIndex == subLen;
}

Considering that the same source string is reused across multiple isSub tests, there's an opportunity to build some sort of index from the source string.

For example, as a simple optimization, you could build a hash set of characters, so that you can check with an \$O(1)\$ operation if a character in sub cannot appear in the source and return false immediately.

A more advanced index would also consider the search position in the source string. So for example if the source string is "haystackkkkkkkkkk" and the sub is "aaa", then after seeing the 2nd "a", the index can tell you that there will be no more "a" and you can return false immediately.

Scanner

No need to wrap System.in in a InputStreamReader, this works just as well:

Scanner scanner = new Scanner(System.in);

Answer 2

Formatting

• Everything inside your class body should be indented by one step further than it currently is.
• Binary operators (+,-, ...) are usually surrounded by one space to make reading them easier

Outputting results

Your if-else statement can be easily replaced by a ternary statement because it IMO is too trivial to actually be worth the effort of reading 5 lines for it.

In other cases I'd advocate against using the ternary, but here it's just so crudely obvious I can't help but recommend using it.

Immutability

It's significantly cleaner to not allow changing your reference string after you read it in. Mark effectively final variables as final explicitly to ease reading.

After applying this handful of changes your code looks as follows:

public class Query {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(new InputStreamReader(System.in));
        final String str = scanner.next();
        int n = scanner.nextInt();
        while (n-- > 0) {
            String sub = scanner.next();
            System.out.println(isSub(str,sub) ? "Yes" : "No");
        }
    }
}