आइए इस समस्या के विवरण से शुरू करते हैं:

आपने संख्याओं की एक स्ट्रिंग के रूप में एन्कोड किया गया एक गुप्त संदेश इंटरसेप्ट किया है। संदेश को निम्नलिखित मैपिंग के माध्यम से डिकोड किया गया है:

"1" -> 'ए' "2" -> 'बी' ... "25" -> 'वाई' "26" -> 'जेड'

हालांकि, संदेश को डिकोड करते समय, आपको एहसास होता है कि आप कई अलग-अलग तरीकों से संदेश को डिकोड कर सकते हैं क्योंकि कुछ कोड अन्य कोड ("2" और "5" बनाम "25") में समाहित होते हैं।

उदाहरण के लिए, "11106" को इस प्रकार डिकोड किया जा सकता है:

• समूह के साथ "एएजेएफ" (1, 1, 10, 6)
• समूह के साथ "केजेएफ" (11, 10, 6)
• समूहीकरण (1, 11, 06) अमान्य है क्योंकि "06" एक वैध कोड नहीं है (केवल "6" मान्य है)।

ध्यान दें: ऐसे तार हो सकते हैं जिन्हें डिकोड करना असंभव हो।

केवल अंकों वाली एक स्ट्रिंग दी गई है, इसे डीकोड करने के तरीकों की संख्या लौटाएं। यदि संपूर्ण स्ट्रिंग को किसी वैध तरीके से डिकोड नहीं किया जा सकता है, तो 0 लौटाएँ।

परीक्षण मामले तैयार किए जाते हैं ताकि उत्तर

32-बिट पूर्णांक में फिट हो जाए।

उदाहरण के लिए:

इनपुट: s = "12" आउटपुट: 2 स्पष्टीकरण: "12" को "एबी" (1 2) या "एल" (12) के रूप में डिकोड किया जा सकता है।

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

या:

इनपुट: s = "226" आउटपुट: 3 स्पष्टीकरण: "226" को "बीजेड" (2 26), "वीएफ" (22 6), या "बीबीएफ" (2 2 6) के रूप में डिकोड किया जा सकता है।

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

या:

इनपुट: s = "06" आउटपुट: 0 स्पष्टीकरण: अग्रणी शून्य ("6" "06" से भिन्न है) के कारण "06" को "एफ" में मैप नहीं किया जा सकता है। इस मामले में, स्ट्रिंग वैध एन्कोडिंग नहीं है, इसलिए 0 लौटाएं।

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

बाधाएँ हैं:

1 s में केवल अंक होते हैं और आगे के शून्य भी हो सकते हैं।

---

मुझे लगता है कि यह उन समस्याओं में से एक है जिसके बारे में आपको लगता है कि पहली नज़र में यह उतना कठिन नहीं है जब तक आप इसे हल करने का प्रयास नहीं करते।

सबसे पहले, आइए सबसे सरल अंतर्दृष्टि से शुरू करें: एक वर्ण को स्वयं (केवल एक वर्ण के रूप में) या दो अंकों की संख्या के भाग के रूप में डिकोड किया जा सकता है।

यदि यह पहला विकल्प है, तो हमारे पास केवल 1 से 9 तक अंक हो सकते हैं, क्योंकि 0 अपने आप में किसी भी चीज़ से मैप नहीं किया जाता है।
हालाँकि, दो अंकों की संख्या 10 से 26 तक हो सकती है।

इस अध्याय में पिछली समस्याओं की तरह, हम स्ट्रिंग के माध्यम से पुनरावृत्ति करते समय प्रत्येक वर्ण को डीकोड करने के तरीकों की संख्या रखने के लिए एक डीपी सरणी बनाकर शुरू कर सकते हैं।

चढ़ने वाली सीढ़ियों के समान, हमें अपनी सरणी को लंबाई s.length 1 के साथ आरंभ करना होगा क्योंकि हमें इस तथ्य पर विचार करने की आवश्यकता है कि हमने अभी तक कुछ भी डिकोड नहीं किया है।
दूसरे शब्दों में, जब कोई अक्षर नहीं होते हैं, तो "डीकोड" करने का केवल
एक तरीका होता है: बिल्कुल भी डिकोड नहीं किया जाता।

इसलिए, हम पहले सूचकांक को छोड़कर, जो 1 होने वाला है, सभी मानों को 0s के रूप में प्रारंभ कर सकते हैं।

let dp = Array.from({ length: s.length 1 }, () => 0); डीपी[0] = 1;

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

फिर से, पिछली समस्याओं के समान, हमें नीचे के दो मान रखने होंगे, इसलिए हमें अपने सरणी के दूसरे स्लॉट को आरंभ करना होगा जो स्ट्रिंग में पहले अक्षर को डिकोड करने के तरीकों की संख्या से मेल खाता है।

हम जानते हैं कि यदि यह '0' है तो हम इसे डिकोड नहीं कर सकते हैं, इसलिए इस मामले में इसे डिकोड करने के तरीकों की संख्या 0 होगी।

ध्यान दें कि
डीकोड करने में सक्षम नहीं होना, बिल्कुल भी डिकोडिंग न करना से अलग है: पहले मामले में, डीकोड करने के तरीकों की संख्या 0 है, लेकिन दूसरे मामले में (जैसे हमने अभी dp[0]) के साथ किया, यह कहा जा सकता है कि डिकोड करने के तरीकों की संख्या 1 है।

अन्य सभी मामलों में, इसे डिकोड करने का केवल

एक तरीका है क्योंकि यह केवल एक ही अक्षर है। तो, हम तदनुसार dp[1] प्रारंभ करेंगे:

डीपी[1] = (एस[0] === '0')? 0 :1;

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

अब हम तीसरे सूचकांक से पुनरावृत्ति शुरू कर सकते हैं। हम एक ही समय में पिछले अंक और पिछले दो अंक दोनों को देखेंगे।

जब तक पिछला अंक संख्या 0 नहीं है, हम अपने सरणी के पिछले स्लॉट में जो कुछ भी है उसे जोड़ सकते हैं।

और, जब तक पिछले दो अंक एक संख्या बनाते हैं जो 10 और 26 के बीच है, हम उस संबंधित समाधान को भी जोड़ सकते हैं। कुल मिलाकर, यह इस तरह दिख सकता है:

के लिए (मान लीजिए i = 2; i Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). इस बिंदु पर, हमारे पास अंतिम सूचकांक में परिणाम है (जो s.length से मेल खाता है) इसलिए हम इसे वापस कर सकते हैं:

फ़ंक्शन numDecodings(s: string): संख्या { /* ... */ वापसी डीपी[एस.लंबाई]; }

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

कुल मिलाकर, हमारा समाधान इस तरह दिखता है:

फ़ंक्शन numDecodings(s: string): संख्या { मान लीजिए dp = Array.from({लंबाई: s.length 1 }, () => 0); डीपी[0] = 1; डीपी[1] = (एस[0] === '0')? 0 :1; के लिए (मान लीजिए i = 2; i Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). समय और स्थान की जटिलता

इस समाधान के लिए समय और स्थान जटिलता दोनों हैं

$O(n)O(n)$पर) चूँकि हम एक निरंतर संचालन करते हुए सभी वर्णों के माध्यम से पुनरावृति करते हैं, और हमें एक सरणी रखनी होगी जिसका आकार हमारे इनपुट आकार के बढ़ने के साथ बढ़ेगा।

---

अगली समस्या सिक्का परिवर्तन नामक है। तब तक, कोडिंग का आनंद लें।