พี>
ตอนนี้เรามีอีกสตริง p งานของเราคือค้นหาว่ามีสตริงย่อยที่ไม่ว่างที่ไม่ซ้ำกันของ p กี่รายการใน s โดยเฉพาะอย่างยิ่ง อินพุตของเราคือสตริง p และเราจำเป็นต้องส่งออกจำนวนสตริงย่อยที่ไม่ว่างที่แตกต่างกันของ p ในสตริง s
ดังนั้นหากอินพุตเป็นเหมือน "zab" เอาต์พุตจะเป็น 6 มีสตริงย่อย "z", "a", "b", "za", "ab", "zab" ของสตริง "zab" ใน สตริง s
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างอาร์เรย์ dp ขนาด 26 ตั้งค่า x :=0
-
สำหรับ I ในช่วง 0 ถึงขนาดของ p
-
ถ้า i> 0 และ (p[i] – p[i – 1] คือ 1 หรือ p[i – 1] – p[i] คือ 25) ให้เพิ่ม x ขึ้น 1 มิฉะนั้น ให้ตั้งค่า x :=1
-
dp[p[i] – ASCII ของ 'a'] :=สูงสุดของ (x, dp[p[i] – ASCII ของ 'a'])
-
-
ยกเลิก :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง 25
-
ret :=ret + dp[i]
-
-
รีเทิร์น
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSubstringInWraproundString(string p) {
vector <int> dp(26);
int x = 0;
for(int i = 0; i < p.size(); i++){
if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
x++;
}
else x = 1;
dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
}
int ret = 0;
for(int i = 0; i < 26; i++){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findSubstringInWraproundString("zab"));
} อินพุต
"zab"
ผลลัพธ์
6
