मान लीजिए हमारे पास दो स्ट्रिंग्स source और target हैं, हमें source के न्यूनतम सबसीक्वेंस की संख्या ढूंढनी है जिन्हें हम बना सकते हैं ताकि यदि हम उन्हें जोड़ दें, तो यह target के समान हो जाए। यदि ऐसा कोई परिणाम नहीं है, तो -1 लौटाएं।
उदाहरण के लिए, यदि इनपुट source = "xyz" target = "xyzyzz" है, तो आउटपुट 3 होगा, क्योंकि हम इन्हें जोड़ सकते हैं ["xyz" + "yz" + "z"]।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- s_size := s का आकार, t_size := t का आकार
- concat_count := 0, target_idx := 0
- जब तक target_idx < t_size, करें
- source_idx := 0
- temp_index := target_idx
- जब तक source_idx < s_size और target_idx < t_size, करें
- यदि s[source_idx], t[target_idx] के समान है, तो
- target_idx := target_idx + 1
- source_idx := source_idx + 1
- यदि s[source_idx], t[target_idx] के समान है, तो
- यदि temp_index, target_idx के समान है, तो
- -1 लौटाएं
- concat_count := concat_count + 1
- concat_count लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, s, t):
s_size, t_size = len(s), len(t)
concat_count = 0
target_idx = 0
while target_idx < t_size:
source_idx = 0
temp_index = target_idx
while source_idx < s_size and target_idx < t_size:
if s[source_idx] == t[target_idx]:
target_idx += 1
source_idx += 1
if temp_index == target_idx:
return -1
concat_count += 1
return concat_count
ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))
इनपुट
"xyz", "xyzyzz"
आउटपुट
3