Цитата(duk @ 13.9.2008, 04:07  ) | | ivg, крут, но все же тот код который привела автор, будет работать быстрее. smile |
Да ну?
В случае двух слов длины n, у автора сложность O(n**2), в то время как у ivg'а лишь жалкие O(n log n). дальнейшее обдумывание показывает что можно и за O(n) уложиться, используя алгоритм аналогичный сортировке подсчетом.
| Код |
import java.util.*;
public class a
{
public
static boolean compareLetters(String s1, String s2){
// можно заменить на массив, особенно если собираются сравнивать гигабайты ДНК
HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
for( int i = 0; i < s1.length(); i++ ){
char c = s1.charAt(i);
Integer j = hash.get(c);
if(j == null){
hash.put(c, 1);
} else {
hash.put(c, 1+j);
}
}
for( int i = 0; i < s2.length(); i++ ){
char c = s2.charAt(i);
Integer j = hash.get(c);
if(j == null){
hash.put(c, -1);
} else {
if( j != 1 )
hash.put(c, j-1);
else
hash.remove(c);
}
}
if( hash.isEmpty() ){
System.out.println( "совпадают" );
return true;
}
System.out.println( "не совпадают" );
return false;
}
public
static void main(String[] main){
assert compareLetters("","") == true;
assert compareLetters("A","a") == false;
assert compareLetters("aba","aaa") == false;
assert compareLetters("aba","aba") == true;
}
}
|
|
