0

回転するテキストの順列の数を取得したい：

私のテキスト：

{abc|{cde|fgh}} aaa {cde|fg}.

結果は6（3x2）になるはずです

ネストされたワードの数に制限がないように順列を取得したいと思います。

どうやってやるの？テキストをフラット化してから3x2{abc|cde|fgh} {cde|fg}を実行しようとしましたが、このテキストをフラット化するにはどうすればよいですか、これに問題があります。誰かが私を助けてくれますか？

これをphpまたはjavascriptで実行したいと思います。

4

1 に答える 1

0

頭に浮かぶ最初の解決策は、再帰的なメソッドを作成することです。

再帰的方法

recursiveメソッドは文字列を受け取り、それを並べ替える方法の数を返します。

ベースケース：

基本ケース：文字列に「{」と「}」がない場合は、「|」の数を返します。文字列の記号に1を加えたもの。

それ以外の場合：

最初の「{」の位置を見つけ、それをPos1と呼びます。

対応する「}」を見つけて、Pos2と呼びます。

ここで、3つのサブストリング[0からPos1）、（Pos1からPos2）、（Pos2からEnd]を形成します。

Pos1とPos2はサブストリングに含まれていないため、2つの中括弧が失われることに注意してください。

各部分文字列の繰り返しの積/合計を返します。

上記のアルゴリズムを示すC＃コードは次のとおりです。

static void Main(string[] args)
{

    string test1 ="{abc|{cde|fgh}} aaa {cde|fg}.";

    int numWays = getNumWaysRecursive(test1);

    Console.WriteLine("NumWays: " + numWays);
    Console.ReadLine();
}

private static int getNumWaysRecursive( string s )
{
    if (s == null) return 1;
    if (s == "") return 1;

    int firstBracePos = s.IndexOf('{');

    if (firstBracePos == -1) //Base case, no braces.
    {
        int pipeCount = 0;

        for (int i = 1; i < s.Length - 1; i++)
        {
            if (s[i] == '|')
            {
                if (pipeCount == -1)
                {
                    pipeCount = 0;
                }
                pipeCount++;
            }
        }

        return pipeCount + 1;
    }

    //Non-Base case:
    // find the first Left Brace
    // find the right brace it corresponds with

    int numOfNests = 0;
    int pos = firstBracePos + 1;

    while (pos < s.Length)
    {
        if (s[pos] == '}')
        {
            numOfNests--;
            if (numOfNests == -1)
            {
                break;
            }
        }

        else if (s[pos] == '{')
        {
            numOfNests++;
        }

        pos++;
    }

    //Get rid of those braces, and recurse on the three parts:
    // 1. the part before the braces.
    // 2. the part between the braces.
    // 3. the part after the braces.

    string firstPart; 
    if (firstBracePos == 0)
    {
        firstPart = "";
    }
    else
    {
        firstPart = s.Substring(0, firstBracePos);
    }

    string secondPart = s.Substring(firstBracePos + 1, pos - firstBracePos - 1);
    string lastPart = s.Substring(pos + 1 );

    int sum1 = getNumWaysRecursive(firstPart); 
    int sum2 = getNumWaysRecursive(secondPart);
    int sum3 = getNumWaysRecursive(lastPart);

    bool strng1HasPipes = (firstPart.IndexOf('|') != -1);

    int sum = 1;

    if ( strng1HasPipes )
    {
        sum += sum1 - 1;
        sum += sum2;
    }
    else
    {
        sum *= sum2;
    }

    if (sum3 == 0)
    {
        ;
    }
    else
    {
        sum *= sum3;
    }

    return sum;
}

残念ながら、これは全体の状況を完全に捉えているわけではありません。

「{abc|{cde | fgh}} aaa {cde | fg} eee | {abc|bbb}」のような文字列では失敗します。

中括弧内にネストされていないため、最後から2番目のパイプシンボルのネスト位置が完全には理解されていないためです。

したがって、文字列の初期スキャンを実行し、「|」に基づいてサブ文字列に分割する必要があります。中括弧内にない記号は、それらの部分文字列の小計を合計します。

于 2012-07-25T05:30:52.707 に答える