Muldawg2020 Muldawg2020 - 1 month ago 7
Java Question

JAVA: comparing a String with a SubString

So here's what I'm trying to accomplish. I'm trying to make a code that does the following from 2 given Strings: a

target
and a
source
.

// Determines whether the string TARGET occurs as a substring of string SOURCE where "gaps" are allowed between characters of target.`
// That is, the characters in TARGET occur in SOURCE in their given order but do not have to be adjacent.`
// (Pictured another way, this method returns true if TARGET could be obtained from SOURCE by removing some of the letters of SOURCE.)`
// This method is case sensitive. For example,`
// containsWithGaps("hamburgers", "mug") returns true`
// containsWithGaps("hamburgers", "burrs") returns true`
// containsWithGaps("hamburgers", "hamburgers") returns true`
// containsWithGaps("hamburgers", "gum") returns false`
// containsWithGaps("hamburgers", "hamm") returns false`
// containsWithGaps("hamburgers", "") returns true`
// Parameters:`
// SOURCE - the given string in which to find the target characters`
// TARGET - the characters to be found`

// Returns:`
// true if the characters in TARGET can be found as a subsequence in SOURCE, false otherwise`


And here's the code I've written. It seems to be overly complicated for what I believe shouldn't be a difficult task, but no matter what, I still keep getting errors and it won't work if given a SOURCE string
hamburgers
with a TARGET string
burr
:

public static boolean substringWithGaps(String source, String target) {

boolean substring = false;
int[] target_index;
target_index = new int [target.length()];

if (target.length() > source.length()) {
substring = false;
}
else {
for (int i = 0; i < target.length(); i++) {
if (source.contains("" + target.charAt(i))) {
target_index[i] = target.indexOf(i);
i++;
}
else {
target_index[i] = target.indexOf(i);
i++;
}
}
for (int i = 0; i < target_index.length; i++) {
if (target_index[i] == -1) {
substring = false;
break;
}
else if (target_index[i] >= target_index[i+1]) {
substring = false;
break;
}
else {
substring = true;
}
if (target_index.length != target.length()) {
substring = false;
}
}
}
return substring;
}


Any ideas?

Answer

Should be pretty simple:

public static boolean substringWithGaps(String source, String target) {
    int targetIndex = 0;
    for (int i = 0; i < source.length(); i++) {
        if (source.charAt(i) == target.charAt(targetIndex)) {
            targetIndex = targetIndex + 1;
            if (targetIndex == target.length()) {
                return true;
            }
        }
    }
    return false;
}

We keep an index of the next letter we need to find within target. Then we loop over source looking for that letter, and when we find it we move the index within target forward one. If the index of target ever equals the length of target, that means we found all of the characters we needed. If we loop over all of source without finding all of target, we return false.