これはインタビューの質問（電話画面）です。特定のテキストに表示される特定の単語のすべての順列を検索する関数を（Javaで）記述します。たとえば、単語abcとテキストabcxyaxbcayxycabの場合、関数はを返す必要がありますabc, bca, cab。
私はこの質問に次のように答えます：
明らかに、指定された単語のすべての順列をループして、標準substring関数を使用できます。ただし、（今のところ私にとっては）すべての単語の順列を生成するコードを書くのは難しいかもしれません。
単語サイズのすべてのテキスト部分文字列をループし、各部分文字列を並べ替えて、「並べ替えられた」指定された単語と比較する方が簡単です。そのような関数をすぐにコーディングできます。
おそらくいくつかの部分文字列検索アルゴリズムを変更できますが、これらのアルゴリズムは今は覚えていません。
この質問にどのように答えますか？
これはおそらくアルゴリズム的に最も効率的なソリューションではありませんが、クラス設計の観点からはクリーンです。このソリューションは、「ソートされた」特定の単語を比較するアプローチを採用しています。
同じ数字に同じ文字が含まれている場合、その単語は別の単語の順列であると言えます。Stringこれは、単語をaから。に変換できることを意味しますMap<Character,Integer>。このような変換は複雑さO（n）になります。ここで、実装Stringの挿入にO（1）のコストがかかると仮定すると、nはの長さです。Map
にはMap、単語で見つかったすべての文字がキーとして含まれ、値として文字の頻度が含まれます。
例。abbcはに変換されます[a->1, b->2, c->1]
bacbはに変換されます[a->1, b->2, c->1]
したがって、2つの単語が一方が他方の順列であるかどうかを知る必要がある場合は、両方をマップに変換してからを呼び出すことができますMap.equals。
次に、テキスト文字列を繰り返し処理し、探している単語と同じ長さのすべてのサブ文字列に変換を適用する必要があります。
Inerdialによって提案された改善
このアプローチは、「ローリング」方式でマップを更新することで改善できます。
i=3つまり、OP（サブストリング）の例のhaystackのインデックスで一致している場合xya、マップはになります[a->1, x->1, y->1]。干し草の山を進むときは、の文字数を減らし、haystack[i]の数を増やしますhaystack[i+needle.length()]。
（動作を確認するためにゼロを削除するかMap.equals()、カスタム比較を実装するだけです。）
マックスによって提案された改善
matchedCharactersCnt変数も導入するとどうなりますか？干し草の山の初めにそれはなります0。マップを目的の値に変更するたびに、変数をインクリメントします。目的の値から変更するたびに、変数をデクリメントします。反復ごとに、変数が針の長さと等しいかどうかを確認します。もしそうなら-あなたは一致を見つけました。毎回完全なマップを比較するよりも高速です。
Maxが提供する擬似コード：
needle = "abbc"
text = "abbcbbabbcaabbca"
needleSize = needle.length()
//Map of needle character counts
targetMap = [a->1, b->2, c->1]
matchedLength = 0
curMap = [a->0, b->0, c->0]
//Initial map initialization
for (int i=0;i<needle.length();i++) {
if (curMap.contains(haystack[i])) {
matchedLength++
curMap[haystack[i]]++
}
}
if (matchedLength == needleSize) {
System.out.println("Match found at: 0");
}
//Search itself
for (int i=0;i<haystack.length()-needle.length();i++) {
int targetValue1 = targetMap[haystack[i]]; //Reading from hashmap, O(1)
int curValue1 = curMap[haystack[i]]; //Another read
//If we are removing beneficial character
if (targetValue1 > 0 && curValue1 > 0 && curValue1 <= targetValue1) {
matchedLength--;
}
curMap[haystack[i]] = curValue1 + 1; //Write to hashmap, O(1)
int targetValue2 = targetMap[haystack[i+needle.length()]] //Read
int curValue2 = curMap[haystack[i+needle.length()]] //Read
//We are adding a beneficial character
if (targetValue2 > 0 && curValue2 < targetValue2) { //If we don't need this letter at all, the amount of matched letters decreases
matchedLength++;
}
curMap[haystack[i+needle.length()]] = curValue2 + 1; //Write
if (matchedLength == needleSize) {
System.out.println("Match found at: "+(i+1));
}
}
//Basically with 4 reads and 2 writes which are
//independent of the size of the needle,
//we get to the maximal possible performance: O(n)
文字列の順列を見つけるには、数論を使用できます。ただし、このアルゴリズムを使用して質問に答える前に、このアルゴリズムの背後にある「理論」を事前に知っておく必要があります。
素数を使って文字列のハッシュを計算できる方法があります。同じ文字列のすべての順列は、同じハッシュ値を与えます。順列ではない他のすべての文字列の組み合わせは、他のハッシュ値を提供します。
ハッシュ値は、c 1 * p 1 + c 2 * p 2 + ... + c n * p nによって計算されます。 ここで、c iは文字列内の現在の文字の一意の値であり、piは一意の素数です。cicharの数値。
これが実装です。
public class Main {
static int[] primes = new int[] { 2, 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 };
public static void main(String[] args) {
final char[] text = "abcxaaabbbccyaxbcayaaaxycab"
.toCharArray();
char[] abc = new char[]{'a','b','c'};
int match = val(abc);
for (int i = 0; i < text.length - 2; i++) {
char[] _123 = new char[]{text[i],text[i+1],text[i+2]};
if(val(_123)==match){
System.out.println(new String(_123) );
}
}
}
static int p(char c) {
return primes[(int)c - (int)'a'];
}
static int val(char[] cs) {
return
p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2];
}
}
これの出力は次のとおりです：abc bca cab
これは1回のパスで実行できるはずです。検索する単語のすべての文字を含むマップを作成することから始めます。したがって、最初はマップにが含まれています[a, b, c]。
次に、一度に1文字ずつテキストを確認します。擬似コードでは、ループは次のようになります。
found_string = "";
for each character in text
if character is in map
remove character from map
append character to found_string
if map is empty
output found_string
found_string = ""
add all characters back to map
end if
else
// not a permutation of the string you're searching for
refresh map with characters from found_string
found_string = ""
end if
end for
一意のオカレンスが必要な場合は、出力ステップを変更して、見つかった文字列をマップに追加します。これにより、重複が排除されます。
重複した文字を含む単語の問題があります。それが問題になる場合は、キーを文字にし、値をカウントにします。文字を「削除」するということは、マップ内のその数を減らすことを意味します。カウントが0になると、そのキャラクターは事実上マップから削除されます。
記述されているアルゴリズムは、重複するオカレンスを検出しません。つまり、テキストが与えられるとabcba、それだけが見つかりますabc。重複するオカレンスを処理する場合は、一致するものが見つかったときに、見つかった文字列の長さを1から引いた値だけインデックスをデクリメントするようにアルゴリズムを変更できます。
それは楽しいパズルでした。ありがとう。
これは私がすることです-STRのその文字が一致したかどうかを示すために0または1に等しい1つの要素を持つフラグ配列を設定します
最初の結果文字列RESULTを空に設定します。
テキストの各文字Cについて：
STRの長さに等しい配列Xをすべてゼロに設定します。
STRの各文字Sについて：CがSTRのJTH文字であり、X [J] == 0の場合、X [J] <= 1に設定し、CをRESULTに追加します。RESULTの長さがSTRと等しい場合は、RESULTを順列のリストに追加し、X[]の要素を再びゼロに設定します。
CがX[J]== 0のSTR内の文字Jでない場合は、X[]の要素を再度ゼロに設定します。
2番目のアプローチは私には非常にエレガントに思え、完全に受け入れられるはずです。でスケーリングされると思いますO(M * N log N)。ここで、Nは単語の長さ、Mはテキストの長さです。
O(M)私はもう少し複雑なアルゴリズムを思い付くことができます：
length(word)）文字についても同じようにしますsubFreqsubFreq、numDiffnumDiffゼロに等しい場合、一致がありますsubFreqますnumDiff編集：いくつかの同様の回答が投稿されていることを確認してください。このアルゴリズムのほとんどは、他の人が提案したローリング周波数カウントと同等です。私の謙虚な追加はまた、ローリング方式で差異の数を更新しO(M+N)、1つではなくアルゴリズムを生成しますO(M*N)。
EDIT2：マックスが基本的にコメントでこれを提案しているのを見たので、ブラウニーは彼を指しています。
このコードは機能するはずです：
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public static void main(String[] args) {
final String word = "abc";
final String text = "abcxaaabbbccyaxbcayxycab";
List<Character> charsActuallyFound = new ArrayList<Character>();
StringBuilder match = new StringBuilder(3);
for (Character c : text.toCharArray()) {
if (word.contains(c.toString()) && !charsActuallyFound.contains(c)) {
charsActuallyFound.add(c);
match.append(c);
if (match.length()==word.length())
{
System.out.println(match);
match = new StringBuilder(3);
charsActuallyFound.clear();
}
} else {
match = new StringBuilder(3);
charsActuallyFound.clear();
}
}
}
}
charsActuallyFound Listは、ループ内ですでに見つかった文字を追跡するために使用されます。「aaa」「bbb」「ccc」（指定したテキストに私が追加したもの）を操作しないようにする必要があります。
さらに熟考した後、私のコードは、指定された単語に重複する文字がない場合にのみ機能すると思います。上記のコードは正しく印刷されます
abc
bca
cab
ただし、「aaa」という単語を検索すると、各文字を2回以上一致させることができないため、何も出力されません。Jim Mischelの回答から着想を得て、コードを編集し、最後に次のようにします。
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public static void main(String[] args) {
final String text = "abcxaaabbbccyaxbcayaaaxycab";
printMatches("aaa", text);
printMatches("abc", text);
}
private static void printMatches(String word, String text) {
System.out.println("matches for "+word +" in "+text+":");
StringBuilder match = new StringBuilder(3);
StringBuilder notYetFounds=new StringBuilder(word);
for (Character c : text.toCharArray()) {
int idx = notYetFounds.indexOf(c.toString());
if (idx!=-1) {
notYetFounds.replace(idx,idx+1,"");
match.append(c);
if (match.length()==word.length())
{
System.out.println(match);
match = new StringBuilder(3);
notYetFounds=new StringBuilder(word);
}
} else {
match = new StringBuilder(3);
notYetFounds=new StringBuilder(word);
}
}
System.out.println();
}
}
これにより、次の出力が得られます。
matches for aaa in abcxaaabbbccyaxbcayaaaxycab:
aaa
aaa
matches for abc in abcxaaabbbccyaxbcayaaaxycab:
abc
bca
cab
いくつかのベンチマークを行いましたが、上記のコードは、わずか4.5秒で36Mのランダムな文字列で30815の「abc」の一致を検出しました。ジムがすでに言ったように、このパズルに感謝します...