puzzling recursion with java

Учитывая строку и непустую подстроку sub, вычислите рекурсивно самую большую подстроку, которая начинается и заканчивается суб и возвращает его длину.puzzling recursion with java

strDist("catcowcat", "cat") → 9 
strDist("catcowcat", "cow") → 3 
strDist("cccatcowcatxx", "cat") → 9

мое решение

public int strDist(String str, String sub) { 
    int i = sub.length(); 
    int j = str.length(); 
    int count = 0; 
    if (str.length() == 1 && str.equals(sub)) { 
     return 1; 
    } else if (str.length() < sub.length() || str.length() <= 1) { 
     return 0; 
    } 

    if (str.substring(0, i).equals(sub)) { 
     if (str.substring(str.length() - i, str.length()).equals(sub)) { 
      return str.length(); 
     } else { 
      strDist(str.substring(0, str.length() - i), sub); 
     } 
    } else { 
     strDist(str.substring(1, str.length()), sub); 
    } 

    return 0; 
}

скажите мне, как исправить мой код?

источник

2014-01-22 user3224959

Это выглядит как прекрасная возможность, чтобы узнать, как использовать отладчик. – NPE

Прежде всего отпечатайте свой код, чтобы лучше видеть объем методов/кодовых блоков/переменных. Это отличная помощь при отслеживании ошибок. – Pshemo

Связанный: http://stackoverflow.com/questions/21292131/1075247/ – Pureferret

Зачем это нужно делать с рекурсией?

Редактировать: фиксированный код для обработки случая, когда суб отсутствует в str или присутствует только один раз.

public int strDist(String str, String sub) { 
    int last=str.lastIndexOf(sub); 
    if (last != -1) { 
    int first=str.indexOf(sub); 
    if (first != last) 
     return last - first + sub.length(); 
    } 
    } 
    return 0; 
}

Рекурсия замечательная, если она подходит к проблеме. В этом случае рекурсия не добавляет значения, а запись ее с рекурсией ради рекурсии делает код неэффективным.

источник

2014-01-22 19:40:16 Trenin

Возможно, это было домашнее задание, поэтому «нужно» вычислить его с рекурсией. – skiwi

попытайтесь запустить код ур с вводом как strDist («xyx», «z») .... это даст неправильный результат ...... проблема с becoz, которую нужно решить путем рекурсии @trenin – user3224959

Просто проверьте, если последний или first == -1, тогда строка не существует и возвращает 0. – ansible

Это будет «вычислить рекурсивно самую большую подстроку, которая начинается и заканчивается суб и возвращает ее длину», как вы описали.

public class PuzzlingRecursion { 

    static String substringFound = ""; 

    public static void main(String[] args) { 
     String sentence = "catcowcat"; 
     String substring = "cat"; 

     int sizeString = findNumberOfStrings(sentence, substring, 0); 
     System.out.println("you are searching for: " + substring); 
     System.out.println("in: " + sentence); 
     System.out.println("substring which starts and ends with sub and return its length is:"+substringFound + ", " + sizeString); 

    } 

    private static int findNumberOfStrings(String subStringPassed, 
      String setenecePassed, int count) { 

     if (subStringPassed.length() == 0) { 
      return count + 0; 
     } 
     if (subStringPassed.length() < setenecePassed.length()) { 
      return count + 0; 
     } 
     count++; 
     String lastStringMiddle = subStringPassed.replaceAll("(.*?)" + "(" 
       + setenecePassed + ")" + "(.*?)" + "(" + setenecePassed + ")" 
       + "(.*?.*)", "$3"); 
     if (subStringPassed.contains(setenecePassed) 
       && lastStringMiddle.length() != setenecePassed.length()) { 
      if (subStringPassed.contains(setenecePassed) 
        && lastStringMiddle.contains(setenecePassed)) { 
       // only found one item no pattern but according to the example 
       // you posted it should return the length of one word/substring 
       count = setenecePassed.length(); 
       substringFound = subStringPassed; 
       return count; 
      } 
     } 
     // makesure the lastSrtringMiddle has the key we are search 
     if (!lastStringMiddle.equals(subStringPassed)) { 
      subStringPassed = subStringPassed.replaceFirst(setenecePassed, ""); 
      String lastString = subStringPassed.substring(0, 
        subStringPassed.lastIndexOf(setenecePassed)); 
      if (null != lastString && !"".equals(lastString)) { 
       count = lastStringMiddle.length() + setenecePassed.length() 
         + setenecePassed.length(); 
       substringFound = setenecePassed + lastStringMiddle 
         + setenecePassed; 
       subStringPassed = ""; 
      } 
      return findNumberOfStrings(subStringPassed, setenecePassed, count); 
     } 
     return count; 
    } 
}

источник

2014-01-23 17:59:55

Я думаю, что это гораздо лучше, рекурсивное решение:

public int strDist(String str, String sub) { 
    if (str.length()==0) return 0; 
    if (!str.startsWith(sub)) 
     return strDist(str.substring(1),sub); 
    if (!str.endsWith(sub)) 
    return strDist(str.substring(0,str.length()-1),sub); 
    return str.length(); 
}

источник

2015-07-13 08:31:51

puzzling recursion with java

ответ

Смежные вопросы