จัดเรียงสตริงตามสตริงอื่น  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ แอคโคไลท์ อะโดบี อเมซอน ฟรีค่าธรรมเนียม InfoEdge ไมโครซอฟท์ Salesforce
การเรียงลำดับ เชือก

คำชี้แจงปัญหา  

ระบุสตริงอินพุตสองแบบคือรูปแบบและสตริง เราจำเป็นต้องจัดเรียงไฟล์ เชือก ตามลำดับที่กำหนดโดยรูปแบบ แบบแผน สตริงไม่มีรายการซ้ำและมีอักขระทั้งหมดของสตริง

รูปแบบการป้อนข้อมูล  

บรรทัดแรกมีสตริง s ที่เราต้องการ ประเภท.

บรรทัดที่สองประกอบด้วยสตริง t ซึ่งไม่มีรายการที่ซ้ำกันและมีอักขระทั้งหมดของสตริง s

รูปแบบผลลัพธ์  

พิมพ์สตริงที่เรียงตามสตริง t

ข้อ จำกัด  

  • 1 <= | s |, | t | <= 10 ^ 6
  • s [i] และ t [j] ต้องเป็นอักขระตัวพิมพ์เล็กเท่านั้น

ตัวอย่าง  

abcedabdceade
ebcda
eeebbccdddaaa

คำอธิบาย: ก่อนอื่นเราจะนับไฟล์ ความถี่ ของแต่ละถ่านที่มีอยู่ในสตริง s ดังนั้นจากตัวอย่างข้างต้น s =“ abcedabdceade” เราจะได้ว่า freq ของ 'a' คือ 3, freq ของ 'b' คือ 2, freq ของ 'c' คือ 2, freq ของ d คือ 3 และ freq ของ e คือ 3 ตอนนี้เราสำรวจสตริง t และตรวจสอบความถี่ของอักขระนั้นและพิมพ์หลาย ๆ ครั้งและย้ายไปยังอักขระถัดไปที่สตริง t และทำซ้ำขั้นตอนเดียวกันจนจบในที่สุดเราก็ได้สตริงที่เรียงลำดับ 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) เพราะเราไม่ได้ใช้พื้นที่เสริมตรงนี้