Is String X a sub sequence of String Y Java

Question

Question copied from https://codegolf.stackexchange.com/questions/5529/is-string-x-a-subsequence-of-string-y

T Given strings X and Y, determine whether X is a subsequence of Y. The empty string is regarded as a subsequence of every string. (E.g., '' and 'anna' are subsequences of 'banana'.)

Is their any function already in Java or some common library which does this ?

Input

X, a possibly-empty case-sensitive alphanumeric string Y, a possibly-empty case-sensitive alphanumeric string Output

True or False (or equivalents), correctly indicating whether X is a subsequence of Y. I/O examples

• '' 'z00' True
• 'z00' 'z00' True
• 'z00' '00z0' False
• 'aa' 'anna' True
• 'anna' 'banana' True
• 'Anna' 'banana' False

Answer 1

You could use regexes to check that the sequence is contained in your search string (and using a replace to interleave your search characters with the wildcard .*):

     String x = "anna";
     String y = "banana";
     x = x.replace("", ".*");  //returns .*a.*n.*n.*a.*

     System.out.println(y.matches(x));  // returns true

Answer 2

Did you look at the String class? y.contains(x) should do all or nearly all of what you require.

I just saw you don't need the sequence grouped. No existing function will do what you want but its reasonably easy to write something:

boolean stringContains(String container, String contents) {
   // start at the start of both strings
   int rpos = 0;
   int cpos = 0;
   // Scan through till we reach the end of either string
   while (rpos<container.length() && cpos<contents.length) {
       // If they match advance both counts, otherwise just
       // move on through the container
       if (container.charAt(rpos) == contents.charAt(cpos)) {
           rpos++;
           cpos++;
       } else {
           rpos++;
       }
   }

   // If we reached the end of the contents string then we have a match
   return cpos==contents.length;
}

Answer 3

You need to remove duplicated characters from both strings, and then you can use String#contains to check for subsequences.

Answer 4

You could use a regex for this:

public boolean subsequence(String superString, String subString) {
    StringBuilder sb = (".*");
    for (char c : subString.toCharArray()) {
        sb.append(c);
        sb.append(".*");
    }
    return superString.matches(sb.toString());
}

This just inserts .* between every character in your matching String, including the beginning and the end.