1

各単語に次の単語と共通する文字が少なくとも 2 つある場合、文字列は2-consistentと呼ばれます。

例えば

「Atom another era」 [ atomhas aand tin common with anotherand anotherhas eand ain common with era(答えは一意ではありません)。

まず、質問で一定時間内に 2 つの単語と回答を受け取るデータ構造が必要です。 "Do these words have at least 2 letters in common?"

ここで、単語の文字列が与えられた場合、最長の 2 つの一貫性のnある部分文字列を見つける必要があります。

使用するデータ構造がわかりません。radix treeかと思ったprefix treeのですが、答えが見つかりませんでした。手伝って頂けますか？

4

3 に答える 3

4

アクセントのない文字を想定し、大文字の使用を無視すると、各単語について、32 ビット整数のビット フィールドを格納できます。az の対応する文字が存在する場合、ビット 0 ～ 25 が 1 に設定されます。

整数は、次のように線形時間で計算できます。

int getBitField(char* word)
{
    int bits = 0;
    while(*word)
        bits |= 1 << ((*word++) - 'a');
    return bits;
}

単語が英語またはその他の言語の単語であり、最大単語長があると想定される場合、(議論のために) 最大長よりも短いすべての単語を埋め込むことができるため、一定時間と線形時間の違いはほとんど意味がありません。一定時間アルゴリズムになります。

2 つの単語のビット フィールドを取得したら、それらを AND 演算し、結果がゼロではないか (共通の文字がないことを示します)、2 のべき乗 (つまり、 1 つのビットのみが設定されているため、1 つの文字のみが共通であることを示します)。2 の累乗は、数値とそれ自体から 1 を引いた値の AND をとることでテストできます。

bool is2Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    return (common & (common - 1)) != 0;
}

これは、'meet' や 'beef' のように文字が繰り返される単語を 2-consistent として定義する場合には機能しません。

3 つの一貫性をテストする場合は、関数に次の行を追加するだけです。

bool is3Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    common &= (common - 1);
    return (common & (common - 1)) != 0;
}

整数とそれ自体から 1 を引いた値の AND を取ると、最下位ビットが削除されるだけなので、任意の回数適用して 4 一貫性、5 一貫性などをテストできます。

于 2015-07-16T08:44:23.453 に答える
2

パート 1:wordOneとwordTwo2 整合性はありますか?

public bool IsWordsTwoConsistent(string first, string second)
{
    int[] letters = Enumerable.Repeat(0, 26).ToArray();
    int countDoubles = 0;

    foreach (char c in first.toLowerCase())
    {
        letters[(int)c - 97]++;
    }

    foreach (char c in second.toLowerCase())
    {
        if (letters[(int)c - 97] > 0)
            countDoubles++;

        if (countDoubles > 1)
            return true;
    }

    return false;
}

パート 2: 最長の 2-consistent 部分文字列

public int GetPositionLongestTwoConsistentSubstring(string input)
{
    string[] wordsArray = input.Split(' ');
    int maxLocation = -1, maxLength = 0;
    int candLocation = -1, candLength = 0;  //candiadate

    for (int i = 0 ; i < wordsArray.Length - 1 ; i++)
    {
        if (IsWordsTwoConsistent(wordsArray[i], wordsArray[i+1]))
        {
            candLength++;
            if (candLocation == -1)
                candLength = i;
        }
        else
        {
            if (candLength > maxLength)
            {
                maxLength = candLength;
                maxLocation = candLocation;
            }           
            candLength = 0;
            candLocation = -1;
        }
    }

    if (candLength > maxLength)
    {
        maxLength = candLength;
        maxLocation = candLocation;
    }

    return maxLocation;
}
于 2015-07-16T07:38:12.147 に答える
1

まず、2 つの単語を取り、「これらの単語には少なくとも 2 文字の共通点がありますか?」という質問に一定時間で答えるデータ構造が必要です。

簡単。最初に、使用している辞書の隣接行列を計算します。ここで、「隣接」は「少なくとも 2 つの文字を共有する」ことを意味するように定義されています。上記のコメントには同意しません。最近では、包括的な英語の辞書を保存することでさえ、それほど多くのデータではありません。完全な隣接行列を格納すると、必要以上にスペースが必要になる場合があるため、疎配列機能を使用してください。

ここで、英語の単語は 26 進数 (大文字を区別する場合は 52 進数) の単なる数字であることを覚えておいてください。そのため、単語のペアの行と列を検索するのは一定時間の操作であり、あなたの質問に対する解決策があります。

確かに、これはスペースを消費し、かなりの量の事前計算が必要ですが、OP は一定時間内に質問に回答するためのデータ構造について尋ねます。

于 2015-07-16T07:46:40.147 に答える