Проверить, если данная строка имеет дубликатов


Описание:

Дана строка найти, если он содержит повторяющиеся символы. Строка содержит только ASCII персонажей.

Код:

import java.util.Arrays;

class Main {
  /**
   * Given a string check if it duplicate characters.
   * []        -> true
   * [f, o, o] -> false
   * [b, a, r] -> true
   * 
   * @param {String} str
   * 
   * @return false if string contains duplicate else true
   */ 
  public static boolean isUnique(String str) {
    if (str.length() == 0) {
      return true;
    }
    boolean[] seen = new boolean[25];
    for (int i = 0; i < str.length(); i++) {
      int index = Character.toLowerCase(str.charAt(i)) - 'a';
      if (seen[index]) {
        return false;
      }
      else {
        seen[index] = true;
      }
    }
    // invariant
    return true;
  }

  public static void main(String[] args) {
    System.out.println(isUnique(""));       // true
    System.out.println(isUnique("a"));      // true
    System.out.println(isUnique("foo"));    // false
    System.out.println(isUnique("bar"));    // true
    System.out.println(isUnique("hello"));  // false
    System.out.println(isUnique("Hello"));  // false
  }
}

Описанных выше алгоритмов выполняется в O(n)в качестве альтернативного решения для сортировки строк и проверить соседние элементы, но это будет O(nlogn). Мне нужно понять, если я правильно используете Java, любые другие родственные стили замечания приветствуются.

PS: Я хотел бы знать, если мне нужно включить больше тестов, чтобы охватить все случаи.



1467
3
задан 26 марта 2018 в 07:03 Источник Поделиться
Комментарии
2 ответа

Несоответствие документации

Документации и функциональность не подходит. Ваша функция должна "проверить если [строка] имеет дубликатов". Из документации, я ожидаю, что функция hasDuplicates что возвращает true если у меня есть повторяющиеся символы и false в противном случае.

Однако, вы предоставляете isUnique, который делает все наоборот: возвращение true если есть никаких дубликатов и false если есть несколько дублей. Внутренней документации подходит, но я бы сказал "проверяет, содержится ли в нем нет повторяющихся символов" или "содержит уникальные персонажи только".

Возможные ошибки

Вы проверили ваши строки только по буквенной строки. Что происходит на "12345678"? Вам будет индексировать -48 из-за '1' - 'a'. Это ошибка ждать, что произойдет. Также, что произойдет, если ваша строка содержит 'z'? Что произойдет, если str это null? Может str не должно быть nullно что следует сделать, указано в документации (см. выше).

Кроме того, следует упомянуть о том, что ваша функция не зависит от регистра. Но почему "Aa" граф как дубликат для начала?

Обоих случаях (не альфа характер и одинаковые буквы в разных случаях) должен быть добавлен в тесты.

Алгоритм

Ваш seen алгоритм-это хорошо, если вы точно знаете, сколько контейнеров вам нужно. Но вы часто не знаете, что. А Map<char,bool> здесь может произойти. Если вы используете TreeMap вы в конечном итоге с указанными \$\mathcal o(п \зарегистрируйте N)\$, но если вы используете HashMap асимптотическая сложность \$\mathcal o(п)\$ снова. Кроме того, используйте набор.

Но это асимптотическая сложность. Если вы не считаете, что любой не-альфа строк (см. раздел выше), то вы можете сразу же вернуть false если строка длиннее 26 персонажи из-за забвению принцип.

4
ответ дан 26 марта 2018 в 07:03 Источник Поделиться


  • Их значительно больше, чем 25 символов ASCII. Вы имели в виду в ASCII буквы? Если тест был для символов, этот код будет перерыв. Но даже если это просто буквы, (дело,) есть 26 букв, а не 25. Попробуйте добавить "пицца" и "сумасшедший" на свой тест, и посмотреть, что происходит. :Р

    Быстрый и грязный решением будет сделать массив 26 элементов.

    Лучшее решение, хотя, может быть использовать HashSet<Character> нежели массив булевских переменных. Пока немного медленнее, он также снимает ограничение "только буквы ASCII". Использовать его как массив: для каждого персонажа, если он уже в наборе, вернуться false; в противном случае добавьте его.


  • Тесты не включают в себя случаи, как, скажем, "Америка" (где верхний и нижний регистр появляются в одно и то же слово). Они должны.

  • Говоря о тестах, вы могли бы рассмотреть, используя фактический рамках тестирования какой-то. System.out.println позволяет увидеть что-то возвращается, что хорошо для только начать...но как-то так Test.assertFalse(isUnique("pizza")) позволит вам выполнить тест, даже если вы не помните, что он должен был делать.

1
ответ дан 26 марта 2018 в 07:03 Источник Поделиться