根據另一個字符串對字符串進行排序  


難度級別 容易獎學金
經常問 埃森哲 ol石 土磚 亞馬遜 免費收費 信息邊緣 Microsoft微軟 Salesforce的
排序

問題陳述  

給定兩個輸入字符串,一個模式和一個字符串。 我們需要對 根據模式定義的順序。 樣式 字符串沒有重複項,並且具有字符串的所有字符。

輸入格式  

第一行包含一個字符串s,我們需要 分類.

第二行包含字符串t,該字符串沒有重複項,並且具有字符串s的所有字符。

輸出格式  

在字符串t的基礎上打印排序後的字符串。

約束  

  • 1 <= | s |,|| t | <= 10 ^ 6
  • s [i]和t [j]只能是小寫字符。

例  

abcedabdceade
ebcda
eeebbccdddaaa

說明: 在這裡,我們先數一下 頻率 字符串s中存在的每個char的整數。 因此,通過上面的示例s =“ abcedabdceade”,我們可以輕鬆地得出“ a”的頻率為3,“ b”的頻率為2,“ c”的頻率為2,d的頻率為3,e的頻率是3。所以,現在我們遍歷字符串t並檢查該char的頻率並打印多次,然後移至字符串t的下一個char並重複相同的步驟直至結束,因此,最後我們得到了排序後的字符串s =“ eeebbccdddaaa”。

算法  

  1. 將輸入字符串的字符數存儲在 頻率[] 數組。
  2. 從左到右遍歷字符串t,對於每個字符t [i],請參見其計數。
  3. 多次打印此字符。
  4. 這樣做直到模式字符串的結尾。
也可以看看
最長子串,無重複字符

根據另一個字符串對字符串排序的實現  

用於根據另一個字符串對字符串排序的C ++程序

#include <bits/stdc++.h>
using namespace std;
 
void SortByPattern(string &s, string t)
{
    int freq[26] = {0};
    int n=s.length();
    int m=t.length();
    for(int i=0;i<n;i++)
    {
        freq[s[i]-'a']++;
    }
    int index = 0;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<freq[t[i]-'a'];j++)
        {
            s[index]=t[i];
            index++;
        }
    }
}

int main()
{
    string s,t;
    cin>>s>>t;
    SortByPattern(s,t);
    cout<<s<<endl;
    return 0;
}

Java程序,用於根據另一個字符串對字符串進行排序

import java.util.Arrays;
import java.util.Scanner;

class sum {
    
    static void SortByPattern(String s, String t)
    {
       int n = s.length();
       int m = t.length();
       char[] s1 = s.toCharArray();
       char[] t1 = t.toCharArray();
       int freq[] = new int[26];
       Arrays.fill(freq, 0);
       for(int i=0;i<n;i++)
       {
           freq[s1[i]-'a']++;
       }
       int index=0;
       for(int i=0;i<m;i++)
       {
           for(int j=0;j<freq[t1[i]-'a'];j++)
           {
               s1[index]=t1[i];
               index++;
           }
       }
       for(int i=0;i<n;i++)
       {
           System.out.print(s1[i]);
       }
    }
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        String s = sr.next();
        String t = sr.next();
        SortByPattern(s,t);
    } 
abcabcabc
bxyzca
bbbcccaaa

根據另一個字符串對字符串進行排序的複雜度分析  

時間複雜度

上) 哪裡 N 是給定數組s的大小。 在這裡,我們遍歷字符串s,這導致我們線性時間複雜度。

空間複雜度

O(1) 因為我們在這裡不使用任何輔助空間。