Geek asks and answers

Recursive method issubtring java

I have the following question:

Write a recursive static isSubstring method with the following signature -

public static boolean isSubstring(String s1,String s2)

receives two lines - s1, s2 and returns true if s2 is a substring for s1.

the method should be recursive without using iterations at all. also any other method you write (if you write).

the correct answer does not change the signature / annotation of the method type (even when overloaded) .

You can use only the following methods in your solution:

public char charAt (int i)

public int length ()

public String substring (int i)

that I still do, I know that this does not work IE isSubstring ("hello", "ho") will return true. any idea what can be done?

public static boolean isSubstring(String s1, String s2) {
    if (s2.length() == 0)
        return true;
    if ((s1.length() == 0) || (s1.length() < s2.length()))
        return false;
    if (s1.charAt(0) != s2.charAt(0))
        return isSubstring(s1.substring(1), s2);
    else
        return isSubstring(s1.substring(1), s2.substring(1));
}
+3
source
4

, .

. , , . , .

public static boolean isSubstring(final String s1, final String s2) {
    if (s2.length() == 0) {
        return true;
    }

    if ((s1.length() == 0) || (s1.length() < s2.length())) {
        return false;
    }

    if (s1.charAt(0) != s2.charAt(0)) {
        return isSubstring(s1.substring(1), s2);
    }

    if (!isSubstringAux(s1.substring(1), s2.substring(1))) {
        return isSubstring(s1.substring(1), s2);
    }

    return true;
}

public static boolean isSubstringAux(final String s1, final String s2) {
    if (s2.length() == 0) {
        return true;
    }

    if (s1.charAt(0) == s2.charAt(0)) {
        return isSubstringAux(s1.substring(1), s2.substring(1));
    }

    return false;
}
+1
public static boolean isSubstring(String s1, String s2) {
    return s2.length() == 0
            || ( s1.length() >= s2.length()
                && ( matchStartOfString( s1, s2 )
                    || isSubstring( s1.substring(1), s2 )
                    )
            );
}

private static boolean matchStartOfString( final String s1, final String s2 )
{
    return s2.length() == 0
            || (    s1.length() >= s2.length()
                &&  s1.charAt( 0 ) == s2.charAt( 0 )
                &&  matchStartOfString( s1.substring(1), s2.substring(1) )
            );
}
+1

, - , . ( , ):

public static boolean sub(final String s1, final String s2, final boolean hasReplaced) {
    if (s2.length() == 0) {
        return true;
    }
    if ((s1.length() == 0) || (s1.length() < s2.length())) {
        return false;
    }
    if (s1.charAt(0) != s2.charAt(0)) {
        if (hasReplaced) {
            return false;
        }
        return sub(s1.substring(1), s2, hasReplaced);
    }
    return sub(s1.substring(1), s2.substring(1), true);
}

public static boolean isSubstring(final String s1, final String s2) {
    return sub(s1, s2, false);
}
0

.

1) . , . , , . 1) 3? false. 2) "bab", true.

2) . , , .

.

public static boolean substringRec(String str, String str2) {
      if (str.length() < str2.length()) return false;
      if (str.length() == str2.length())
      {
          if (equals(str, str2))
            return true;
          return false;
      }
      else
        return substringRec(str.substring(1), str2);    
}

public static boolean equals(String str1, String str2)
{
    if (str1.charAt(0) == str2.charAt(0))
    {
        if (str1.length() == 1)
            return true;

        return equals(str1.substring(1), str2.substring(1));                
    }
    return false;
}

, . , . .equals, , , , .

, .

? , , ln (n), n - . , , . 1 000 000 ! 14 .

, , , , , .

1) , false. 2) , , true, else false. 3) , true.

, .

, , , .

public static boolean substringRec2(String str, String searchString) {       

      // Base cases
      if (str.length() < searchString.length()) 
          return false;

      if (str.length() == searchString.length())
      {
          if (str.equals(searchString))
          {
              return true;
          }
          return false;
      }

      int halfWay = str.length()/2;

      // Now check for the search string over the "break"
      for (int i = 0; i < searchString.length(); i++)
      {
          int startIndex = halfWay - 1 - i;
          int endIndex = startIndex + 3;
          if (startIndex >= 0)
          {
              String substring = str.substring(startIndex, endIndex);
              if (substring.equals(searchString))
              {
                  return true;
              }
          }
      }

     // Recursive Cases 
     //  We did find the search string over the break,so break the string into two equal(ish) pieces and check those 
     if(substringRec2(str.substring(0,halfWay -1), searchString))
         return true;

     if(substringRec2(str.substring(halfWay, str.length()), searchString))
         return true;

     return false;
}

- - fooobar.com/questions/2107434/...

0

More articles:


All Articles