2017-09-04 12 views
0

与えられた文字列(古典的なインタビューの質問)から重複を取り除くタスクがありますが、これは少し異なります。最終結果は最小の辞書順その他。たとえば、cbacdcbc => acdb, bcabc => abcとなります。私はSOのいくつかの関連する問題を見ましたが、答えを見つけることができませんでした。最小の辞書順を維持しながら重複する文字を削除する方法

編集:ここでは、これまでに(正常に動作していない)私のコードです:

public static String removeDuplicateCharsAlphbetically(String str) { 
    int len = str.length(); 
    if (len<2) return str; 

    char[] letters = str.toCharArray(); 
    int[] counts = new int[26]; 
    for (char c : letters) { 
     counts[c-97]++; 
    } 

    StringBuilder sb = new StringBuilder(); 

    for (int i=0;i<len-1;i++) { 
     if (letters[i]==letters[i+1]) continue; 

     if (counts[letters[i]-97]==1) { 
      sb.append(letters[i]); 
     } else if (counts[letters[i]-97] != 0) { 
      if (letters[i]<letters[i+1] && counts[letters[i]-97] == 1) { 
       sb.append(letters[i]); 
       counts[letters[i]-97]=0; 
      } else { 
       counts[letters[i]-97]--; 
      } 
     } 

    } 

    return sb.toString(); 
} 

EDIT2:私は質問以前のリンクを入れていないため申し訳ありません。ここではlink

+0

なぜPythonがタグ付けされていますか? –

+0

私はPythonまたはJava – Humoyun

+0

のいずれかで解決策が必要です。*最小の辞書順ではどういう意味ですか? **ただ一つの**辞書順です。最初の例で '' b''の前に '' c ''が来るのはなぜですか? –

答えて

1

最初に、文字列sのすべての別個の文字のセットを作成しましょう。このセットのサイズは、解答の長さとアルゴリズムのステップ数です。アルファベット順に残りの文字を反復処理

あらゆる段階で、すべての文字lのために: 我々は、次の貪欲なアプローチで、各ステップでの回答に1つの文字を追加します

  1. の最初の出現を探しますlsに設定します。それをlposと名をつけましょう。
  2. サブストリングs[lpos, end]に残りの文字がすべて含まれている場合は、結果にlを追加し、ss[lpos+1, end]に置き換え、残りの文字を減らして次のステップに進みます。

良い時間の複雑性を達成するために、いくつかの最適化と実装:

public String removeDuplicateLetters(String s) { 
    StringBuilder result = new StringBuilder(); 
    int[] subsets = new int[s.length()]; 

    int subset = 0; 
    for (int i = s.length() - 1; i >= 0; i--) { 
     char ch = s.charAt(i); 
     subset = addToSet(subset, ch); 
     subsets[i] = subset; 
    } 

    int curPos = 0; 
    while (subset != 0) { 
     for (char ch = 'a'; ch <= 'z'; ++ch) { 
      if (inSet(subset, ch)) { 
       int chPos = s.indexOf(ch, curPos); 
       if (includes(subsets[chPos], subset)) { 
        result.append(ch); 
        subset = removeFromSet(subset, ch); 
        curPos = chPos + 1; 
        break; 
       } 
      } 
     } 
    } 

    return result.toString(); 
} 

private boolean inSet(int set, char ch) { 
    return (set & (1 << (ch - 'a'))) != 0;  
} 

private boolean includes(int set, int subset) { 
    return (set | subset) == set; 
} 

private int addToSet(int set, char ch) { 
    return set | (1 << (ch - 'a')); 
} 

private int removeFromSet(int set, char ch) { 
    return set & ~(1 << (ch - 'a')); 
} 

たRunnableバージョン:https://ideone.com/wIKi3x

+0

あなたが解決に費やした時間と労力のために大変ありがとうございます – Humoyun

1

観測1:出力の最初の文字は、他のすべての文字が文字列の一番左の外観の右側に表示されるような最小の文字です。

観測2:出力の残りの文字は、最初の文字の最も左の外観の右側の文字の部分列です。

これは再帰的アルゴリズムを示唆しています。

def rem_dups_lex_least(s): 
    if not s: 
     return '' 
    n = len(set(s)) # number of distinct letters in s 
    seen = set()  # number of distinct letters seen while scanning right to left 
    for j in range(len(s) - 1, -1, -1): # len(s)-1 down to 0 
     seen.add(s[j]) 
     if len(seen) == n: # all letters seen 
      first = min(s[:j+1]) 
      i = s.index(first) # leftmost appearance 
      return first + rem_dups_lex_least(''.join(c for c in s[i+1:] if c != first)) 
1

開始するために、入力の終わりから逆方向に行くことによって、結果をビルドします。各ステップで:

  1. 新しい文字がある場合は、結果の前に追加します。
  2. 重複が発生した場合は、結果の先頭と比較してください。 headが大きい場合は、結果から重複を削除し、代わりに前に追加します。

LinkedHashSetは、結果セットとその内部順序の両方を格納するのに適しています。

public static String unduplicate(String input) { 
    Character head = null; 
    Set<Character> set = new LinkedHashSet<>(); 
    for (int i = input.length() - 1; i >= 0; --i) { 
     Character c = input.charAt(i); 
     if (set.add(c)) 
      head = c; 
     else if (c.compareTo(head) < 0) { 
      set.remove(c); 
      set.add(head = c); 
     } 
    } 
    StringBuilder result = new StringBuilder(set.size()); 
    for (Character c: set) 
     result.append(c); 
    return result.reverse().toString(); 
} 
+1

良い解決策ですが、間違っているようです。テスト: 'abacb'、答え:' abc'。このアルゴリズムは 'acb'を返します。 – DAle

関連する問題