Рекурсивное программирование Longestword

Question

Я сделал это, наконец, как я хочу.Спасибо всем за помощь, и я хочу подчеркнуть, что это НЕ домашняя работа.

public static void main(String[] args) {
    String input = "Java is a programming language";
            StringTokenizer st = new StringTokenizer(input);
    System.out.print(longestWord(input));

}

public static String longestWord(StringTokenizer st) {
    if (!st.hasMoreTokens()) {
        return "";

    } else {
        String token = st.nextToken(); 
        String longestInTheRest = longestWord(st);
        if (token.length() > longestInTheRest.length()) { 

            return token;

        } else {
            return longestInTheRest;
        }

Answer 1

Следующее не совсем верно:

else if (token.length() > result.length()) {

Когда выполняется вышеприведенный оператор, result всегда " ".

Что функция должна сделать, так это вернуть большее из: (1) длины token; (2) длина слова, возвращаемого рекурсивным вызовом.

Вы также можете подумать о том, выполняют ли два вызова s.substring() именно то, что вам нужно, или могут возникнуть проблемы. Распечатка token и rest (или проверка их в отладчике) может быть полезной.

Так как это похоже на домашнюю работу, я остановлюсь здесь.

Answer 2

Другое решение, написанное в более функциональном стиле - обратите внимание, что я не выделяю новые строки при каждом вызове рекурсивного метода (только операция split в начале выделяет новые строки).Я также принял предложение Роберта сначала преобразовать исходную проблему в рекурсию по массивам, это упростит задачу:

public static String longestWord(String s) {
    return longestWord(s.split("\\s+"), 0, 0);
}

public static String longestWord(String[] words, int currentIdx, int longestIdx) {
    if (currentIdx == words.length)
        return words[longestIdx];
    return longestWord(words, currentIdx + 1,
        words[currentIdx].length() > words[longestIdx].length() ? currentIdx : longestIdx);
}

Хитрость в приведенном выше решении заключается в том, что моя рекурсия опережает индексы 1006 * массива строк, а не поверх самих строк.Вот почему я избегаю создавать новые строки при каждом вызове.Нет substring, copyOfRange, arraycopy, new String() или аналогичные операции необходимы для получения более элегантного решения.

РЕДАКТИРОВАТЬ:

Я упростилприведенный выше код немного, чтобы было легче понять.Что касается метода split, это стандартная строковая операция, взгляните на документацию .

public static String longestWord(String s) {        
    return longestWord(s.split(" "), 0, 0);
}

public static String longestWord(String[] words, int currentIdx, int longestIdx) {
    if (currentIdx == words.length)
        return words[longestIdx];
    int idx;  // temporarily stores the index of the current longest word
    if (words[currentIdx].length() > words[longestIdx].length())
        idx = currentIdx;
    else
        idx = longestIdx;
    return longestWord(words, currentIdx + 1, idx);
}

Answer 3

Вы сравниваете текущее слово с результатом, но результатом является локальная переменная, которая всегда имеет значение " " (кстати, это не пустая строка, а строка, содержащая пробел).

Вы должны передать текущий результат в качестве аргумента методу и начать с пустой строки в качестве результата.

У вас также есть ошибка, потому что вы не обрезаете свои токены и, следовательно, рассматриваете начальный пробел как часть слова.

Answer 4

Я бы выбрал немного другой подход для решения этой проблемы:

Во-первых, я бы преобразовал строку в массив, который лучше подходит для рекурсивного метода.

public static String longestWord(String string) {
    return longestWord(string.split(" "), "");
}

Тогда мы можем подумать о рекурсивном методе. Если мы рекурсивно передаем меньший массив, мы знаем, что в итоге мы передадим пустой массив - это наш базовый случай, мы перечислили все элементы, поэтому просто возвращаем самый длинный, который был передан в качестве параметра. В рекурсивном случае мы проверяем, больше ли первый элемент (теперь меньшего) массива, чем текущий самый длинный, и рекурсивно вызываем передачу в более длинном из двух.

private static String longestWord(String[] strings, String currentLongest) {
    if (strings == null || strings.length == 0) {
        return currentLongest;
    }
    String[] newStrings = Arrays.copyOfRange(strings, 1, strings.length);
    String longest = strings[0].length() < currentLongest.length() ? currentLongest : strings[0];
    return longestWord(newStrings, longest);
}

Примечание. Этого также можно добиться, используя индексы в массиве, а не копируя его. Однако на практике эта оптимизация слишком далека - она ​​усложняет чтение и вряд ли принесет кому-либо пользу.

Answer 5

Вам нужно проверить, осталось ли место.

Что-то вроде

int index = s.indexOf(' ');
if (index < 0) return s;

Answer 6

    result = token;
    return longestWord(rest);

это не та часть. Результат сохраняет токен, но затем вы выходите из метода, вводите его снова и устанавливаете результат в «». Добавьте еще один параметр String currentLongest в сигнатуру метода, чтобы он не потерялся.

Answer 7

Чтобы вернуться к работе, вам нужно передать текущее состояние, самое длинное слово, с которым нужно сравнить.

Если выглядит как домашнее задание, поэтому я не включаю ответ - пожалуйста, дайте мнезнаю, если это не так.