1

問題は、与えられた文字列 s から辞書編集的に最大の文字列を生成することです。したがって、目的は、s から辞書編集的に最大の一意の (繰り返しのない) 部分文字列 s1 を見つけることです。あるサブシーケンス s1 が別のサブシーケンス s2 よりも大きいとは、s1 が s2 よりも文字数が多い場合、または s1 が辞書編集的に s2 よりも長さが等しい場合です。

I/O は次のとおりです。

入力は: ba bab

出力は次のとおりです。

2番目の入力は次のとおりです。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

2 番目の出力: tsocrpkijgdqnbafhmle

これは私が Java コード用に書いたものですが、私のコードは 2 番目のテスト ケースで失敗します。また、2 番目の出力が tsrqponmlkjihgfedcba ではない理由を理解するのに苦労しています。誰かが修正や Java コードの提案を提供できますか?

アルゴリズムは、可能なすべての一意の文字列を生成し、それらを並べ替えて、辞書編集的に最大のものを見つけるよりも効率的でなければならないと思います。

質問をより明確にするために、入力が babab の場合、可能な一意の組み合わせはすべて b、a、ba、ab になります。出力は ba になります。これは、ab よりも長く、辞書編集的に大きいためです。

注：これは宿題ではありません。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class mostBeautiful {
final static int MAX = 1000000;
static String[] permute;
static void permutation(String prefix, String str, int counter) {
    int n = str.length();
    //System.out.println("n is: "+ n);
    if (n == 0) {
        permute[counter] = prefix;
    } else {
        for (int i = 0; i < n; i++) {
            //System.out.println("str is: "+ str);
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), counter++);
        }
    }
}
public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String s = bf.readLine();
    char[] unique = new char[26];
    int counter = 0;
    String answer = "";
    //System.out.println("s is: " + s);
    int ascii = 0;
    final int asciiAVal = 97;
    final int asciiZVal = 122;
    for (int i = 0; i < s.length(); i++) {
        ascii = (int)s.charAt(i);
        if (ascii < asciiAVal || ascii > asciiZVal) {
            continue;
        }
        char ch = s.charAt(i);
        unique[ch - 'a'] = ch;
    }
    String result = "";
    for (int j = 25; j >= 0; j--) {
        result += unique[j];
    }
    result = result.trim();
    System.out.println(result);
    int size = result.length() * (result.length() - 1);
    permute = new String[size];
    permutation("", result, counter);
    for (int i = 1; i < size; i++) {
        if (permute[i].compareTo(permute[i - 1]) > 0){
            answer = permute[i];
        }  else {
            answer = permute[i - 1];
        }

    }
    System.out.println("answer is: " + answer);
}

}

4

5 に答える 5

2

この問題についてさまざまな方法で検討した結果、正しい結果が得られる分割統治アルゴリズムを決定しました。

アルゴリズム - 疑似コード

入力文字列 S が 2 つの部分文字列 A + B の連結として定義されていると仮定すると、次のように辞書編集的に最大の文字列を再帰的に計算します。

LexMax(S) = Merge(LexMax(A),LexMax(B))

どこ

LexMax(S)
{
    if Length(S) = 1
        return S
    else
    {
        LMA = LexMax(S[0:Length/2])
        LMB = LexMax(S[Length/2:end])
        return Merge(LMA,LMB)
    }
}

Merge(A,B)
{
    Sa = A
    Sb = B

    for n = 0:Length(A)
    {
        if Sb contains A[n]
        {
            if A[n+1:end] contains character > A[n]
                Remove A[n] from Sa
            else
                Remove A[n] from Sb
        }
    }

    return Sa + Sb
}

Java コード

近日公開！

例

与えられた入力文字列

cefcfdabbcfed

に分けます

cefcfda
bbcfed

関数が機能すると仮定すると、次のようになります。

LexMax("cefcfda") = "efcda"
LexMax("bbcfed") = "bcfed"

マージは次のように機能します。

e: efcda bcfed

両方の部分文字列で、左側の部分文字列の e の右側に大きな値が見つかり、左側から削除

f: fcda bcfed

両方の部分文字列で、左側の部分文字列に大きな値はなく、右側から削除

c: fcda bced

両方の部分文字列で、左側の部分文字列の c の右側に大きな値が見つかり、左側から削除

d: fda bced

両方の部分文字列で、左側の部分文字列に大きな値はなく、右側から削除

a: fda bce

両方の部分文字列にない、何もしない

最終結果：

LexMax(cefcfdabbcfed) = fdabce
于 2012-07-10T00:32:43.660 に答える
1

これは直接的な答えではありませんが、上記の説明で説明したように、このコードは要件を満たしていませんか？

final String x = "saontehusanoethusnaoteusnaoetuh";
final SortedSet<Character> chars = 
   new TreeSet<Character>(Collections.reverseOrder());
for (char c : x.toCharArray()) chars.add(c);
System.out.println(chars);
于 2012-07-09T10:08:24.787 に答える
1

辞書式順序は、単語内の文字の出現を使用して、単語がアルファベット順に表示される順序です。辞書順またはアルファベット順とも呼ばれます。たとえば、「アフリカ」は「バングラデシュ」よりも小さく、「彼」 「彼」より小さいです。

 public class LexicographicExample {  
      public static void main(String a[]) {  
           Scanner sc = new Scanner(System.in);  
           System.out.println("Enter the String:-");  
           String str = sc.nextLine();  
           System.out.println("Enter the length");  
           int count = sc.nextInt();  
           List<String> list = new ArrayList<String>();  
           for (int i = 0; i < str.length(); i = i + 1) {  
                if (str.length() - i >= count) {  
                     list.add(str.substring(i, count + i));  
                }  
           }  
           Collections.sort(list);  
           System.out.println("Smallest subString:-" + list.get(0));  
           System.out.println("Largest subString:-" + list.get(list.size() - 1));  
      }  
 }

参考までに、このリンクを参照してくださいhttp://techno-terminal.blogspot.in/2015/09/java-program-to-find-lexicographically.html

于 2015-11-17T06:33:47.167 に答える
0

「tsrqponmlkjihgfedcba」は入力のサブシーケンスではないため、答えではありません。サブシーケンスの定義では、サブシーケンスの文字が元のシーケンスに同じ順序で出現する必要があります。たとえば、「abc」は「apbqcr」のサブシーケンスですが、「cba」はそうではありません。

解決策としては、単純な貪欲なアルゴリズムで十分だと思います。まず、出力の可能な最大長は、入力内の一意のシンボルの数 (たとえば、N) であることを理解する必要があります。それより短い出力は最大のものではないため、正確に N シンボルの長さでなければなりません。手順の残りの部分は単純で、時間の複雑さはせいぜい 2 次です。入力文字列を調べて、各ステップで、文字列の左側の部分にすべての "未使用」の記号。

例として、文字列「bacb」を考えてみましょう。最初の記号は 'a' または 'b' です。どちらの場合も、残りの部分には他の文字が両方含まれているからです。'b' の方が大きいので、それを選択します。現在、「acb」の場合、その条件に従って「a」と「c」のみを選択できるため、出力は「bac」になります。

于 2012-07-09T14:04:26.643 に答える