определить, если строка имеет уникальные символы

Question

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

я увидел решение, но не совсем понимаю.

public boolean isUniqueChars(String str) { 
    if (str.length() > 256) return false; 
    boolean[] char_set = new boolean[256]; 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i); 
     if (char_set[val]) 
      return false; 
     char_set[val] = true; 
    } 
    return true; 
} 

Разве мы не используем parseInt или (int) преобразователь перед кодом? (будет str.charAt[i] автоматически изменен на int?) Что boolean[] char set=new boolean[256] значит? Почему мы должны установить char_set[val]=true?

Answer 1

Смотрите мое объяснение в комментариях, так как вы только маркированные algorithm я не имею ни одного языка, предполагая и просто решить алгоритм себя:

public boolean isUniqueChars(String str){ 

    //more than 256 chars means at least one is not unique 
    //please see first comment by @Domagoj as to why 256 length 
    if(str.length()>256) return false; 

     //keeping an array to see which chars have been used 
     boolean[] char_set = new boolean[256]; 

     //iterating over the string 
     for(int i=0; i<str,length;i++){ 

      //not sure what language this is, but let's say it returns an 
      //int representation of the char 
      int val=str.charAt(i); 

      //meaning this has been set to true before, so this char is not unique 
      if(char_set[val]) 
       //nope, not unique 
       return false; 

      //remember this char for next time 
      char_set[val]=true; 
     } 

    //if we reached here, then string is unique 
    return true; 
} 

Answer 2

Подумайте о том, как вы могли бы сделать это с карандашом и бумагой.

Выпишите алфавит один раз.

Затем перейдите к символу строки.

Когда вы достигли символа, перечеркните его из своего алфавита.

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

Это, по сути, код, который вы опубликовали, используя массив. Операция завершается в O (N) раз с дополнительным пространством O (K) (где K - это количество ключей, которые у вас есть).

Если ваш вход имел большое количество элементов или вы не могли знать, что они были раньше времени, вы можете использовать hash table, чтобы отслеживать, какие элементы уже были замечены. Это снова приводит к O (N) времени с O (cK) дополнительным пространством, где K - это количество ключей, а c - некоторое значение, превышающее 1.

Но таблицы хэша могут занимать довольно много места. Есть еще один способ сделать это. Сортируйте массив, который займет время O (N log N), но для которого требуется no дополнительное пространство. Затем пройдите по массиву, чтобы проверить, совпадают ли какие-либо два соседних символа. Если это так, у вас есть дубликат.

Answer 3

Мы также можем использовать HashSet Структура данных, чтобы определить, есть ли строка имеет все уникальные символы в java.

Set testSet = new HashSet(); 

for (int i = 0; i < str.length(); i++) { 
    testSet.add(new Character(str.charAt(i))); 
} 

if (testSet.size() == str.length()) { 
    System.out.println("All charcaters are Unique"); 
} else { 
    System.out.println("All charcaters are niot unique"); 
}