ZeroJudge E507: Common Permutation

同題：UVa 10252 – Common Permutation

給定兩個由小寫字母組成的字串 a 和 b。

印出最長的小寫字串 x，使得 x 經過重新排列後為 a 的子序列，且 x 經過重新排列後為b的子序列。

範例測資

範例輸入範例輸出
EOF 輸入，連續的兩行為一組，第一行為字串 a，第二行為字串 b。
1～2 行為一組輸入，3～4 行為一組輸入，依此類推。
每個字串最多包涵1000個小寫字母。		對於每組輸入，輸出本題要求 a 和 b 的 x。
如果有多組符合的x
請印出字母順序由小到大排列的那一個。
pretty
women
walking
down
the
street		e
nw
et

解題思路

使用 Map 來紀錄 a 的有哪些字元，再跑 b 的 For迴圈 看這個字元有沒有在A有出現過，如果有的話就在答案的 Map 裡面紀錄，並且將 A 的 Map -1。

使用 for (auto it:Map) 跑 答案Map 的迴圈將字元輸出。

範例程式碼－ZeroJudge E507: Common Permutation

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string a, b;
    while (cin >> a >> b)
    {
        map<char, int>A;
        map<char, int>ans;
        for (int i = 0; i<a.length(); i++)
        {
            A[a[i]]++;
        }
        for (int i = 0; i<b.length(); i++)
        {
            if (A[b[i]] > 0)
            {
                ans[b[i]]++;
                A[b[i]]--;
            }
        }
        for (auto it:ans)
        {
            for (int i = 0; i<it.second; i++)
            {
                cout << it.first;
            }
        }
        cout << "\n";
    }
}

//ZeroJudge E507
//Dr. SeanXD
標籤

相關文章

發佈留言