両方の文字列を O(nlogn) 時間で並べ替えた後、2 つの文字列がアナグラムであるかどうかを見つけることができますが、o(n) 時間と O(1) 空間でそれを見つけることは可能です。
9490 次
12 に答える
5
素数配列を生成する [26] 各素数は文字を表し、文字列をトラバースすると、各文字の素数を倍増させます。等しい場合はアナグラムであり、そうでない場合はそうではありません。O（n）と一定のスペースが必要です
于 2012-09-09T18:42:06.430 に答える
5
ここには絶対に専門家はいません...
しかし、各文字列を調べて、各文字が何回出現するかを単純に数えてみませんか.
適切な実装があれば、これには O(n) 時間以上かかることはありません。
于 2011-07-11T05:32:17.850 に答える
5
それを解決するにはいくつかの方法があります。
方法 1 - カスタム ハッシュ コード関数
を使用する 次のような hashCode 関数を使用できます。
static int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
static String alphabet = "abcdefghijklmnopqrstuvwxyz";
public static int hashCode(String s){
int sum = 0;
for(char c: s.toCharArray()){
sum += primes[c-97];
}
return sum;
}
両方の文字列のハッシュを生成し、hashCode が等しい場合、文字列はアナグラムです。このメソッドは、何らかの方法で文字列の hashCode を生成するため、Jin が言及したソリューションに似ています。
時間の複雑さ - O(n)
方法 2 - 文字と整数のハッシュマップを使用する
2 つの文字列を文字の 2 つの配列と見なします。最初の配列をトラバースし、文字とカウントのハッシュマップに文字を追加し、文字が見つかったらカウントを増やします。同様に、2 番目の配列をトラバースし、ハッシュマップのカウンターをデクリメントします。文字が見つからない場合、それらはアナグラムではありません。最後に、マップにすべての文字があり、カウントが 0 の場合、再び 2 つの文字列がアナグラムになります。
方法 3 - カウント配列を使用する (私のお気に入り)
boolean are_anagrams(string1, string2){
let counts = new int[26];
for each char c in lower_case(string1)
counts[(int)c]++
for each char c in lower_case(string2)
counts[(int)c]--
for each int count in counts
if count != 0
return false
return true
}
ここですべてのコードを取得できます。
于 2014-04-26T12:04:57.863 に答える
4
はい、ハッシュを使用して出現回数を数えます。最後にゼロ以外の数字がある場合、文字列はアナグラムではありません。
let h => hash which maps letters to occurence_count (initialized to 0)
for each letter l in string a
h[l] = h[l] + 1
end
for each letter l in string b
h[l] = h[l] - 1
end
for each key l in h
return false if h[l] != 0
end
return true
これは O(n) + O(n) + c = O(n)で実行されます。ハッシュには 26 文字のスポットが含まれており、それぞれに整数が関連付けられています。したがって、スペースは O(26) = O(1)です。
[[編集]]、上記と同じですが、時間分析の注釈があります:
let h => hash which maps letters to occurence_count (initialized to 0)
#this loop runs n times
for each letter l in string a
#hash lookups / writes are constant time
h[l] = h[l] + 1
end
#above function ran O(n) time
for each letter l in string b
h[l] = h[l] - 1
end
#runs in O(alphabet) = O(c) = constant-time
for each key l in h
return false if h[l] != 0
end
return true
于 2011-07-11T05:32:45.297 に答える
1
で実行:O(n) + O(n) = O(n)
使用済みスペースを修正:O(256) = O(1)
ここにJavaのコードがあります
private static boolean isAnagramWithOneArray(String strFirst, String strSecond) {
int[] charsCount = new int[256];
if (strFirst != null && strSecond != null) {
if (strFirst.length() != strSecond.length()) {
return false;
}
for (int i = 0; i < strFirst.length(); i++) {
charsCount[strFirst.charAt(i)]++;
charsCount[strSecond.charAt(i)]--;
}
for (int i = 0; i < charsCount.length; i++) {
if (charsCount[i] != 0) {
return false;
}
}
return true;
} else {
return (strFirst == null && strSecond == null);
}
}
于 2013-01-16T08:10:28.760 に答える
0
私はそれを以下のようにします：
//is s an anagram of t?
#include <string>
bool is_anagram(const string& s, const string& t)
{
bool ret = false;
//if s and t are anagrams, they must of same size
if( s.length() != t.length() )
{
return ret;
}
//assume that s and t have valid ascii characters only
char letters[ 256 ] = {0};
int i;
// find occurence of each character in string s
for( i = 0; i < s.length(); i++ )
{
(letters[ s[i] ])++;
}
// now, find occurence of each character in string t, but decrement
// correspnding character
for( i = 0; i < t.length(); i++ )
{
//if the count is <0 means the given character is not present in s
if( --(letters[ t[i] ]) < 0 )
{
return ret;
}
}
//out of for loop means success
ret = true;
return ret;
}
于 2014-08-01T07:09:10.813 に答える
0
ここでのすべての提案は、入力文字列を並べ替えてから結果を比較するという同じアプローチを使用する傾向があります。通常のASCII文字に主に関心があるため、これは、ほとんどの回答者のアプローチと思われるカウントソートによって最適化できます。カウントソートはO(n)の数字・整数の限られたアルファベットのソートができるので技術的には正解です。後で count 配列をトラバースする時間を考慮する必要がある場合は、アルファベットの時間が含まれるため、アルファベットが UTF-32 の場合、O(m+n) がやや正確な上限になります。
アルファベットを十分に制限できない場合、クイックソートの方がリアルタイムで高速であることが証明される可能性があるため、最も一般的に正しいアプローチには O(n lg n) が必要であると考える傾向があります。
于 2014-04-26T12:18:12.087 に答える
0
並べ替えられた順序で単語の文字を変換し、文字列をハッシュするとします。ソート後に同じハッシュを持つすべての文字列は、他の文字列のアナグラム (非常に可能性が高く、常に衝突の可能性があります) になります。
于 2011-07-11T05:31:33.270 に答える
0
上記のコードは、すべての条件で機能しません
代わりに、すばやく並べ替えて、スペースを削除しながら配列を比較できます
于 2013-01-10T17:13:07.793 に答える
0
Pythonを使用してこのようなものはありますか？
def anagram(a,b):
s1=list(a)
s2=list(b)
for i in s1:
if i in s2:
s2.remove(i)
print(s2)
return len(s2)==0
文字列が互いにアナグラムでない場合、これは false を返します。
remove などのビルトインの使用を避けるには、次のアプローチを使用できますか?
def hana(a,b):
s1=list(a.lower())
s2=list(b.lower())
print(s1,s2)
h={'a': 0, 'c': 0, 'b': 0, 'e': 0, 'd': 0, 'g': 0, 'f': 0, 'i': 0, 'h': 0, 'k': 0,'j': 0, 'm': 0, 'l': 0, 'o': 0, 'n': 0, 'q': 0, 'p': 0, 's': 0, 'r': 0, 'u': 0, 't': 0, 'w': 0, 'v': 0, 'y': 0, 'x': 0, 'z': 0}
for i in s1:
h[i]+=1
for i in s2:
h[i]-=1
for key, val in h.items():
if val != 0:
return False
return(True)
文字列が互いのアナグラムである場合、最終的なハッシュはすべてのキーに対して値 0 を持つ必要があります。0 以外の場合は、文字が繰り返されているか、他の文字列に存在しない文字があり、アナグラムではないことを意味します。
于 2021-05-15T19:23:44.050 に答える
-1
たぶん次のようなものです：
String str1 = "test";
String str2 = "tzet";
int count = 0;
for (int i = 0; i < str1.length(); i++)
{
count = count + str1.charAt(i) - str2.charAt(i);
}
System.out.println(count);
文字列 2 からすべての文字を減算し、文字列 1 からすべての文字をカウントに追加します (ASCII 文字を想定)。アナグラムの場合、count は 0 になります。
ただし、これは、スペースが挿入されたアナグラムを考慮していません。
于 2011-07-13T17:54:06.010 に答える