لنبدأ بوصف هذه المشكلة:

لقد اعترضت رسالة سرية مشفرة كسلسلة من الأرقام. تم فك تشفير الرسالة عبر التعيين التالي:

"1" -> 'أ' "2" -> 'ب' ... "25" -> 'ص' "26" -> 'ض'

ومع ذلك، أثناء فك تشفير الرسالة، تدرك أن هناك العديد من الطرق المختلفة التي يمكنك من خلالها فك تشفير الرسالة لأن بعض الرموز موجودة في رموز أخرى ("2" و"5" مقابل "25").

على سبيل المثال، يمكن فك تشفير "11106" إلى:

• "AAJF" مع المجموعة (1، 1، 10، 6)
• "KJF" مع المجموعة (11، 10، 6)
• التجميع (1، 11، 06) غير صالح لأن "06" ليس رمزًا صالحًا (فقط "6" صالح).

ملاحظة: قد تكون هناك سلاسل من المستحيل فك تشفيرها.

نظرًا لسلسلة تحتوي على أرقام فقط، قم بإرجاع عدد الطرق لفك تشفيرها. إذا لم يكن من الممكن فك تشفير السلسلة بأكملها بأي طريقة صالحة، قم بإرجاع 0. يتم إنشاء حالات الاختبار بحيث تتناسب الإجابة مع عدد صحيح

32 بت

.

على سبيل المثال:

الإدخال: الصورة = "12" الإخراج: 2 توضيح: يمكن فك تشفير "12" كـ "AB" (1 2) أو "L" (12).

Input: s = "12"

Output: 2

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

الإدخال: الصورة = "226" الإخراج: 3 توضيح: يمكن فك تشفير "226" كـ "BZ" (2 26)، أو "VF" (22 6)، أو "BBF" (2 2 6).

Input: s = "12"

Output: 2

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

الإدخال: الصورة = "06" الإخراج: 0 Explanation: لا يمكن ترجمة "06" إلى "F" بسبب الصفر البادئ ("6" يختلف عن "06"). في هذه الحالة، السلسلة ليست ترميزًا صالحًا، لذا قم بإرجاع 0.

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

1

تحتوي s على أرقام فقط وقد تحتوي على أصفار بادئة.

أعتقد أن هذه إحدى المشكلات التي تعتقد أنها ليست صعبة للغاية للوهلة الأولى حتى تحاول حلها.

---

أولاً، لنبدأ بأبسط فكرة: يمكن فك تشفير الحرف إما على أنه نفسه (كحرف واحد فقط) أو جزء من رقم مكون من رقمين.

إذا كان هذا هو الخيار الأول، فيمكننا فقط الحصول على أرقام من 1 إلى 9، حيث أن 0 في حد ذاته لا يتم تعيينه لأي شيء.

ومع ذلك، يمكن أن يكون الرقم المكون من رقمين من 10 إلى 26.

كما هو الحال مع المشاكل السابقة في هذا الفصل، يمكننا البدء بإنشاء مصفوفة dp لاستيعاب عدد الطرق لفك تشفير كل حرف أثناء تكرارنا للسلسلة.

مشابه جدًا لـ Climbing Stairs، علينا تهيئة مصفوفتنا بالطول s.length 1 حيث نحتاج إلى الأخذ في الاعتبار حقيقة أننا لم نفك تشفير أي شيء بعد.

بمعنى آخر، عندما لا يكون هناك أحرف، هناك طريقة
واحدة فقط لـ "فك التشفير": عدم فك التشفير على الإطلاق.
لذلك، يمكننا تهيئة جميع القيم على أنها 0، باستثناء الفهرس الأول الذي سيكون 1.

let dp = Array.from({ length: s.length 1 }, () => 0); موانئ دبي[0] = 1;

مرة أخرى، على غرار المشاكل السابقة، علينا الاحتفاظ بالقيمتين السفليتين، لذلك يتعين علينا تهيئة الفتحة الثانية من المصفوفة التي تتوافق مع عدد الطرق لفك تشفير الحرف الأول في السلسلة.

let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;

نحن نعلم أنه لا يمكننا فك تشفيره إذا كان "0"، لذا فإن عدد طرق فك تشفيره سيكون 0 في هذه الحالة.

لاحظ أن

عدم القدرة على فك التشفير

يختلف عن
عدم القيام بأي فك تشفير على الإطلاق: في الحالة الأولى، عدد طرق فك التشفير هو 0، ولكن في الحالة الثانية (كما لقد فعلنا ذلك للتو مع dp[0])، ويمكن القول أن عدد طرق فك التشفير هو 1. في جميع الحالات الأخرى، هناك طريقة واحدة فقط لفك تشفيرها لأنها مجرد حرف واحد. لذلك، سنقوم بتهيئة dp[1] وفقًا لذلك:

dp[1] = (s[0] === '0') ؟ 0 : 1;
الآن يمكننا البدء بالتكرار من الفهرس الثالث. سننظر إلى كل من الرقم السابق والرقمين السابقين في نفس الوقت.

dp[1] = (s[0] === '0') ? 0 : 1;

وطالما أن الرقمين السابقين يشكلان رقمًا يتراوح بين 10 و 26، فيمكننا إضافة هذا الحل المقابل أيضًا. بشكل عام، يمكن أن يبدو الأمر كما يلي:

لـ (دع i = 2؛ i

for (let i = 2; i 
ملحوظة نقوم بتحويل أحرف السلسلة إلى أرقام باستخدام عامل التشغيل الأحادي الزائد المفيد. نعلم من قيود المشكلة أن السلسلة تحتوي على أرقام فقط.في هذه المرحلة، لدينا النتيجة في الفهرس الأخير (الذي يتوافق مع s.length) لذا يمكننا إعادتها فقط:

 الدالة numDecodings(s: string): الرقم {
  /* ... */

  إرجاع dp[s.length]; 
}





بشكل عام، هكذا يبدو الحل الذي نقدمه:
let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;
 الدالة numDecodings(s: string): الرقم {
  Let dp = Array.from({ length: s.length 1 }, () => 0);

  موانئ دبي[0] = 1;
  موانئ دبي[1] = (s[0] === '0') ؟ 0 : 1;

  لـ (دع i = 2؛ i 





  
  
  تعقيد الزمان والمكان


function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length   1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i 


  
 
 
    ($)O\; (ن)على)$
 أثناء قيامنا بالتكرار عبر جميع الشخصيات التي تقوم بعملية مستمرة، وعلينا الاحتفاظ بمصفوفة سينمو حجمها مع زيادة حجم الإدخال لدينا.




المشكلة التالية هي المشكلة التي تسمى Coin Change. حتى ذلك الحين، برمجة سعيدة.