CODEWITHSUNDEEP
javastringrecursion
John Smith
John Smith

Reputation: 167

Recursive string comparison

I am trying to compare two strings, to see if one string contains the other one and what point. So basically I am trying to find indexOf. However, I don't want use it.

This is the code I have written that works perfectly using indexOf:

import java.lang.*;

public class Index
{
  public static void indexOf(String main, String check)
  {
    System.out.println(main.toLowerCase().indexOf(check.toLowerCase()));
  }
  public static void main(String[] args)
  {
    indexOf("Barack Obama", "Obama");
  }
}

However, the problem is that I don't want to use indexOf. Furthermore, I am trying to make the code recursive.

So I tried writing this code:

public class Index
{
  public static int indexOf(String main, String check)
  {

    int n = check.length();
    int i = main.length();

    int h = 0;

    for (int j = 0; j < n; j++)
    {
      if (main.charAt(j) == check.charAt(j)) h++;
    }
    return h - 1;
  }
  public static void main(String[] args)
  {
    System.out.println(indexOf("Barack", "B"));
  }
}

However, this one doesn't work at all how it is supposed to and it isn't even recursive.

Is there anyway, I can make this method recursive and not use indexOf?

Upvotes: 1

Views: 190

Answers (3)

Akshay Patil
Akshay Patil

Reputation: 78

This works fine too, if you also don't want to use startsWith(). Here a part of check String is matched with the main String if previous part is all matched.

public class Index {

    public static int indexOf(String main, String check) {

        int i = main.length();

        for (int j = 0; j < i; j++) {
            if (main.charAt(j) == check.charAt(0)) {
                if (check.length() > 1) {
                    if (indexOf(main, check.substring(1)) == j + 1) {
                        return j;
                    }
                } else {
                    return j;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(indexOf("My name is XYZ", "ashfbs"));//returns -1;
        System.out.println(indexOf("My name is XYZ", "is"));//returns 8;
    }
}

Upvotes: 1

user1886323
user1886323

Reputation: 1199

package com.company;

public class Index {
    public static int indexOf(String main, String check)
    {
        if (main.startsWith(check)) {
            return 0;
        } else if (main.length() < check.length()) {
            return -1;
        } else {
            int indexOf = indexOf(main.substring(1), check);
            return indexOf < 0 ? -1 : 1 + indexOf;
        }
    }
    public static void main(String[] args)
    {
        System.out.println(indexOf("Barack Obama", "Obama"));
    }
}

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

Before making a method recursive it is beneficial to think about your task in recursive terms. What does it mean for a sub-string to start at a specific index of a string? One way to explain it recursively is as follows:

An index of a sub-string is

  • -1, if the string is shorter than the substring
  • 0, if your string begins with the sub-string, or
  • 1 + index of the sub-string, when the first character of the string has been removed, and the return value is positive
  • -1 if index of the sub-string returned -1

Highlighted portion indicates the spot where recursion has been applied: in order to compute the index of a sub-string we must compute the index of a sub-string in a shorter string.

This description can be converted to a recursive method almost literally:

int indexOf(String str, String sub) {
    if (str.length() < sub.length()) return -1;
    if (str.startsWith(sub)) return 0;
    int res = indexOf(str.substring(1), sub);
    return res < 0 ? res : 1+res;
}

Demo.

Upvotes: 3

Related Questions