Cách ngắn nhất để tạo chuỗi trong C ++

Giả sử chúng ta có một chuỗi, chúng ta có thể tạo một dãy con của chuỗi đó bằng cách xóa một số ký tự (có thể không xóa). Vì vậy, nếu có hai chuỗi nguồn và đích, chúng ta phải tìm số lượng nhỏ nhất của chuỗi nguồn sao cho nối của chúng bằng đích. Nếu nhiệm vụ là không thể, thì trả về -1. Vì vậy, nếu nguồn là "abc" và đích là "abcbc", thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một chuỗi được gọi là có thể, điều này sẽ lấy s và t làm đầu vào

• tạo bản đồ m

• đối với mỗi ký tự c trong s đánh dấu m [c]:=1

• đối với mỗi ký tự c trong t, nếu m [c] bằng 0 thì trả về false

• trả về true

• Bây giờ từ phương thức chính, hãy làm như sau -

• ssz:=kích thước của s và tsz:=kích thước của t

• tạo một bản đồ m gồm khóa kiểu ký tự và giá trị kiểu mảng

• cho tôi trong phạm vi từ 0 đến ssz

  • chèn tôi vào m [s [i]]

• pre:=-1 và ret:=1

• cho tôi trong phạm vi từ 0 đến tsz

  • nếu t [i] không có trong m, trả về -1

  • v:=m [t [i]]

  • đặt i:=chỉ mục của phần tử trong v, lớn hơn trước

  • nếu tôi không phải là người cuối cùng của danh sách

    • tăng ret lên 1 và pre:=v [0]

  • nếu không thì trước:=v [i]

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"abc"
"abcbc"

Đầu ra

2