Word Break

Q: ما هو التعقيد الزمني لمسألة تقسيم الكلمات؟

يعمل الجدول التصاعدي مع مجموعة تجزئة بتعقيد O(m × L + n × L²) ، حيث إن n هو طول s ، و m هو عدد الكلمات، و L هي أطول كلمة. وتكلف مقارنة كل كلمة عند كل موضع O(n × m × L) . أما الاستدعاء الذاتي البسيط فتعقيده أُسّي.

Q: هل مسألة تقسيم الكلمات مسألة برمجة ديناميكية أم مسألة رسوم بيانية؟

كلاهما. في البرمجة الديناميكية، تشير canEnd[i] إلى ما إذا كان من الممكن تقسيم أول i حرفًا. وفي الرسم البياني، يكون كل فهرس عقدة، وتوجد حافة من i إلى j عندما تشكّل الحروف بينهما كلمة، ويكون السؤال هو ما إذا كان يمكن الوصول إلى n انطلاقًا من 0. ينفّذ البحث بعرض أول العمل نفسه الذي ينفّذه الجدول.

متوسطالبرمجة الديناميكية التجزئة

+10

لديك سلسلة نصية s وقائمة كلمات wordDict. أعد true إذا كان بإمكانك تقسيم s إلى أجزاء تكون جميعها كلمات من wordDict، وأعد false خلاف ذلك.

تحافظ الأجزاء على ترتيبها وتستخدم معًا كل حرف من s مرة واحدة بالضبط. يمكن استخدام الكلمة أي عدد من المرات، ولا يلزمك استخدام كل الكلمات.

الدالة

wordBreak(s: string, wordDict: string-array) → boolean

sstring: السلسلة المراد تقسيمها إلى كلمات
wordDictstring-array: الكلمات التي يمكنك استخدامها، كلٌّ منها بالقدر الذي تشاء
تُرجعboolean: صحيح إذا أمكن تقسيم s إلى كلمات من القاموس، وخطأ خلاف ذلك

القيود

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s وتحتوي كل كلمة على أحرف إنجليزية صغيرة فقط.
الكلمات الموجودة في wordDict كلها مختلفة.

أمثلة

المدخلات: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
المخرجات: true
الشرح: قسّمها إلى sun وflower وseed. أخذ flow بعد sun يترك er، وهي بداية لا تبدأ بها أي كلمة، لذا فإن أول كلمة تناسب ليس دائمًا الخيار الصحيح.

المدخلات: s = "bananaban"wordDict = ["ban", "ana"]
المخرجات: true
الشرح: تغطي ban + ana + ban السلسلة وتستخدم ban مرتين، وهذا مسموح.

المدخلات: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
المخرجات: false
الشرح: كلٌّ من pine + apple وpineapple يترك tart. لا يناسبه سوى tar، وهذا يترك t وحيدة، لذا لا ينجح أي تقسيم.

سؤال إضافي

أعِد أقل عدد من الكلمات التي يمكن أن يستخدمها تقسيم صالح، أو -1 إذا تعذّر تقسيم s. ما الذي يتغير في الجدول، وهل يتغير زمن التنفيذ؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

إن الالتزام بكلمة واحدة في كل مرة لا ينجح، كما أن تجربة كل موضع قطع تستغرق وقتًا أُسّيًا. لكن إمكانية تقسيم بقية s تعتمد فقط على موضع بدايتها، لذا لا يوجد سوى n + 1 سؤالًا. أدناه، n هو طول s، وm هو عدد الكلمات، وL هو طول أطول كلمة.

جرّب كل كلمة في كل موضع

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

يجب أن تكون القطعة الأولى كلمةً تبدأ بها s. جرّب كل كلمة من هذا النوع، واطرح السؤال نفسه عن الأحرف المتبقية؛ فالباقي الفارغ يعني أن كل حرف قد قُسِّم. تجربة كل كلمة أولى، ثم كل كلمة ثانية، لا يمكن أن تفوّت تقسيمًا صالحًا.

يتحقق من البواقي نفسها مرارًا وتكرارًا. مع 299 نسخة من a تتبعها نسخة واحدة من b، والكلمات a وaa وصولًا إلى عشر نسخ من a، تصل أكثر من 10^89 طريقة لتقسيم أحرف a إلى كتل إلى b وتفشل، وتجربها عملية الاستدعاء الذاتي كلها.

الخوارزمية

اكتب canSplit(start): هل يمكن تقسيم الأحرف من start حتى النهاية؟ إذا كان start يساوي طول s، فأعِد true.
لكل كلمة يحتوي عليها s عند الفهرس start، إذا كانت canSplit(start + its length) تساوي true، فأعِد true.
وإلا فأعِد false. الإجابة هي canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

الاستدعاء الذاتي مع التخزين المؤقت

الفكرة

تعتمد الإجابة المتعلقة بالباقي فقط على start، الذي يأخذ n + 1 قيمة. في مثال الحرف a، يُبلَغ الباقي عند الفهرس 20 بعد كتلتين من عشرة، وبعد عشرين حرفًا منفردًا a، وبطرق أخرى لا تُحصى، وتكون النتيجة false في كل مرة. خزّن إجابة كل قيمة من قيم start مرة واحدة وأعِد استخدامها.

يجب أن تحتفظ المذكرة بإجابات false. فإجابة true تنهي البحث كله فورًا، لذا يحدث كل العمل المتكرر في الفروع التي تفشل.

تجرّب كل قيمة start كل كلمة، مع مقارنة ما يصل إلى L أحرف: زمن O(n × m × L)، وبحد أقصى 6 × 10^6 فحصًا للأحرف، ومساحة O(n).

الخوارزمية

أنشئ جدولًا للتخزين المؤقت يحتوي على خانة لكل فهرس، واجعل علامة كل خانة «لم يُحسب بعد».
في canSplit(start)، أرجِع true عند نهاية s، أو أرجِع الإجابة المخزنة إذا كانت الخانة تحتوي عليها.
وإلا فجرّب كل كلمة كما في الاستدعاء الذاتي البسيط، وخزّن النتيجة في الخانة، بما في ذلك false، ثم أرجِعها.

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

من الأسفل إلى الأعلى عبر البوادئ باستخدام مجموعة تجزئة

الفكرة

اعمل على البادئات. لتكن canEnd[i] محدِّدةً ما إذا كان يمكن تقطيع الأحرف i الأولى؛ وتكون canEnd[0] هي true، لأن البادئة الفارغة لا تحتاج إلى كلمات. يمكن تقطيع الأحرف end الأولى بالضبط عندما تكون قطعتها الأخيرة، من start إلى end، كلمةً وتكون canEnd[start] هي true. وبملئها من اليسار إلى اليمين، ستكون كل قيمة canEnd[start] تحتاج إليها معروفةً مسبقًا.

ضع الكلمات في مجموعة تجزئة. لا توجد كلمة أطول من L، لذا لا يمكن أن تطابق، مهما كبر القاموس، سوى القطع الـ L التي تنتهي عند end. في sunflowerseed، تكون canEnd صحيحة عند 0 و3 و7 و9 و13؛ ولا تسبّب النهاية المسدودة عند 7 أي مشكلة.

يفحص كل موضع من المواضع n ما لا يزيد عن L من القطع، وتستغرق كل منها ما يصل إلى L خطوات لبنائها وحساب تجزئتها: O(n × L²)، أي ما يصل إلى 1.2 × 10^5 خطوة، بالإضافة إلى O(m × L) للمجموعة.

الخوارزمية

ضع الكلمات في مجموعة تجزئة؛ ولاحظ أطول طول L.
أنشئ canEnd مع n + 1 مدخلات، كلها false، واجعل canEnd[0] تساوي true.
لكل end من 1 إلى n ولكل length من 1 إلى min(L, end): إذا كانت canEnd[end-length] تساوي true وكان الجزء بهذا الطول والمنتهي عند end موجودًا في المجموعة، فاجعل canEnd[end] تساوي true وتوقف.
أعِد canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

أخطاء شائعة وحالات حدّية

التقطيع بأسلوب جشع. يقطّع اختيار الأطول أولًا carpetal إلى carpet ويترك al بلا استخدام، مع أن car + petal تنجح؛ أما اختيار الأقصر أولًا فيتعثر عند sunflowerseed.
تخزين الإجابات true فقط في الذاكرة المؤقتة. يتكرر العمل في الفروع false، لذا يظل مثال الأحرف a أُسّيًا.
جعل الجدول أقصر بمدخل واحد. يحتاج canEnd إلى n + 1 مدخلًا، لأطوال البادئات من 0 إلى n.
المقارنة بعد نهاية s، مثل مقارنة الكلمة abc بما تبقى وهو ab. تحقّق من الأطوال أولًا.
في Lua وR، تبدأ مواضع السلاسل النصية من 1: فالجزء ذو الطول k الذي ينتهي عند الحرف e يبدأ عند e-k+1.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة تقسيم الكلمات؟

يعمل الجدول التصاعدي مع مجموعة تجزئة بتعقيد O(m × L + n × L²)، حيث إن n هو طول s، وm هو عدد الكلمات، وL هي أطول كلمة. وتكلف مقارنة كل كلمة عند كل موضع O(n × m × L). أما الاستدعاء الذاتي البسيط فتعقيده أُسّي.

هل مسألة تقسيم الكلمات مسألة برمجة ديناميكية أم مسألة رسوم بيانية؟

كلاهما. في البرمجة الديناميكية، تشير canEnd[i] إلى ما إذا كان من الممكن تقسيم أول i حرفًا. وفي الرسم البياني، يكون كل فهرس عقدة، وتوجد حافة من i إلى j عندما تشكّل الحروف بينهما كلمة، ويكون السؤال هو ما إذا كان يمكن الوصول إلى n انطلاقًا من 0. ينفّذ البحث بعرض أول العمل نفسه الذي ينفّذه الجدول.

كيف تعرض كل جملة بدلًا من إرجاع true أو false؟

التراجع: عند كل فهرس جرّب كل كلمة تناسب، واستدعِ الدالة递归يًا على الجزء المتبقي، وتذكّر قائمة الجمل لكل فهرس. أنشئ جدول الصواب أو الخطأ أولًا، حتى تتجاوز البحث عن سلسلة لا يمكن تقسيمها. يمكن أن يزداد عدد الجمل نموًا أُسّيًا، لذا يحدد حجم الناتج زمن التنفيذ.

def wordBreak(s, wordDict):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

الإخراج المتوقع

true

Word Break

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كل كلمة في كل موضع

الاستدعاء الذاتي مع التخزين المؤقت

من الأسفل إلى الأعلى عبر البوادئ باستخدام مجموعة تجزئة

أخطاء شائعة وحالات حدّية

أسئلة شائعة3

مسائل مشابهة