วิธีที่สั้นที่สุดในการสร้างสตริงใน C ++

สมมติว่าเรามีสตริง เราสามารถสร้างลำดับของสตริงนั้นได้โดยการลบอักขระบางตัว (อาจไม่มีการลบ) ดังนั้นหากมีสตริงต้นทางและเป้าหมายสองสตริง เราต้องหาจำนวนลำดับย่อยของซอร์สขั้นต่ำเพื่อให้การเรียงต่อกันเท่ากับเป้าหมาย หากงานนั้นเป็นไปไม่ได้ ให้คืนค่า -1 ดังนั้นหากแหล่งที่มาคือ "abc" และเป้าหมายคือ "abcbc" ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสตริงที่เรียกว่า เป็นไปได้ ซึ่งจะใช้ s และ t เป็นอินพุต

• สร้างแผนที่ ม

• สำหรับแต่ละอักขระ c ใน s เครื่องหมาย m[c] :=1

• สำหรับแต่ละอักขระ c ใน t ถ้า m[c] เป็น 0 ให้คืนค่าเท็จ

• คืนความจริง

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ssz :=ขนาดของ s และ tsz :=ขนาดของ t

• สร้างแผนที่ m ของคีย์ประเภทอักขระและค่าประเภทอาร์เรย์

• สำหรับฉันอยู่ในช่วง 0 ถึง ssz

  • แทรก i ลงใน m[s[i]]

• ก่อน :=-1 และ ret :=1

• สำหรับฉันอยู่ในช่วง 0 ถึง tsz

  • ถ้า t[i] ไม่มีอยู่ใน m ให้คืนค่า -1

  • v :=m[t[i]]

  • set i :=ดัชนีขององค์ประกอบใน v ที่มากกว่า pre

  • ถ้าฉันไม่ใช่จุดสิ้นสุดของรายการ

    • เพิ่ม ret โดย 1 และก่อน :=v[0]

  • อย่างอื่นก่อน :=v[i]

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

อินพุต

"abc"
"abcbc"

ผลลัพธ์

2