JAVA: comparing a String with a SubString

Question

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?

Pseaudocode: String foo = source.replace(/\s+/, "", g); if (-1 != foo.indexOf(target) { hooray() } — Tibrogargan
– Tibrogargan, Commented Oct 11, 2016 at 23:31
Just this source.contains(target), in Java would work fine. — Jorge Campos
– Jorge Campos, Commented Oct 11, 2016 at 23:31
@Jorge Campos No, that will not satisfy the requirements - it will return true only if the target is exactly in the source. The requirement is that there can be intervening letters, — FredK
– FredK, Commented Oct 11, 2016 at 23:43

nhouser9 · Accepted Answer · 2016-10-11 23:31:43Z

2

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.

answered Oct 11, 2016 at 23:31

nhouser9

6,7803 gold badges23 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user4910279 Over a year ago

StringIndexOutOfBoundsException when target=""

Muldawg2020 Over a year ago

Yea but that's what I don't seem to understand. take source = "hamburger" and target = "burr" On line 4 of your code, ` if (source.charAt(i) == target.charAt(targetIndex)) {` the targetIndex would stay at 0 until the loop iterated over b in hamburger, whose index# is 3, but targetIndex should still be at 0, so they would never equal.

Muldawg2020 Over a year ago

@saka1029 I added in if (target == ""){return true; } to the top and it seems to work fine after that

Muldawg2020 Over a year ago

Omg I'm an idiot. Okay I understand it now, hahathanks!

nhouser9 Over a year ago

@Muldawg2020 You ask why targetIndex stays at 0 in this code. targetIndex refers to the index of the string target. So the value of targetIndex SHOULD be 0 when searching for "b", while the index of source is allowed to move forward. Download the code and run it yourself if you don't think it works. I already tested it and got correct results.

Pradeep Pati · Accepted Answer · 2016-10-11 23:44:54Z

0

The following should do it.

public static boolean containsWithGaps(String a, String b){
    if(b.length() > a.length())
    {
      return false;
    }
    char[] targetChars = new char[b.length()];
    b.getChars(0,b.length(),targetChars, 0);
    int pos = 0;
    for(char myChar : targetChars)
    {
      pos = a.indexOf(myChar, pos);
      if(pos == -1)
      {
        return false;
      }
    }
    return true;
  }

answered Oct 11, 2016 at 23:44

Pradeep Pati

5,9293 gold badges31 silver badges43 bronze badges

Comments

Tibrogargan · Accepted Answer · 2016-10-12 02:13:13Z

0

Slight optimization in that it returns as soon as a character could not be matched (and doesn't crash if target is zero length)

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

answered Oct 12, 2016 at 2:13

Tibrogargan

4,6323 gold badges21 silver badges41 bronze badges

Collectives™ on Stack Overflow

JAVA: comparing a String with a SubString

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related