Word Break

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

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

Q: هل تُعدّ مشكلة Word Break مسألة برمجة ديناميكية أم مسألة رسوم بيانية؟

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

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

+10

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

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

الدالة

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

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

القيود

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 وحيدًا، لذا لا يصلح أي تقسيم.

+21 اختبارات مخفية عند الإرسال

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

يفشل التقطيع الجشع في كلا الاتجاهين: فأخذ أقصر كلمة أولًا يقسّم sunflowerseed إلى sun + flow، وأخذ أطول كلمة أولًا يقسّم carpetal إلى carpet ويترك al دون تقسيم. لذا عليك تجربة الخيارات، ويمكن تقسيم سلسلة نصية بطرق كثيرة أُسّيًا. وما يحل المشكلة هو أن إمكانية تقسيم بقية السلسلة تعتمد فقط على موضع بدايتها، لذلك لا توجد سوى n + 1 أسئلة مختلفة. أدناه، n هو طول s، وm هو عدد الكلمات، وL هو طول أطول كلمة.

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

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

الفكرة

اقرأ s من اليسار. أيًّا كانت القطعة الأولى، فلا بد أن تكون كلمة يبدأ بها s. جرّب كل كلمة من هذا النوع، واسأل عن الأحرف المتبقية السؤال نفسه لكل واحدة منها. إذا أدّت أي كلمة إلى تقسيم كامل، فالإجابة هي true. وإذا لم تؤدِّ أيٌّ منها إلى ذلك، فالإجابة هي false. عندما لا يتبقى شيء، تكون قد قسمت كل حرف، وهذا يُعدّ نجاحًا.

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

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

الخوارزمية

اكتب دالة مساعدة canSplit(start) تحدد ما إذا كان بالإمكان تقسيم الأحرف من الفهرس start حتى النهاية إلى كلمات.
إذا كان start يساوي طول s، فأعِد true.
تحقّق لكل كلمة مما إذا كان s يحتوي عليها بدءًا من الفهرس start.
إذا كان كذلك وكانت canSplit(start + length of the word) تساوي 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 في كل مرة. خزّن الإجابة لكل بداية في أول مرة تحسبها فيها، ثم اقرأها لاحقًا.

تحتاج خانة التخزين المؤقت إلى ثلاث حالات: لم تُحسب بعد، وtrue وfalse. إجابات false هي المهمة. تنهي إجابة true البحث كله فورًا، لذا فإن العمل الذي تكرره العودية العادية يقتصر على الفروع التي تفشل.

تُحسب كل بداية مرة واحدة وتجرّب كل كلمة، مع مقارنة ما يصل إلى L أحرف، لذا فالزمن هو O(n × m × L): بحد أقصى 300 × 1000 × 20 = 6 × 10^6 عملية فحص للأحرف هنا. يشغل التخزين المؤقت ومكدس الاستدعاءات مساحة O(n)، وتتداخل الاستدعاءات بعمق يصل إلى 300.

الخوارزمية

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

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] تحتاج إليها معروفةً بالفعل.

بدلًا من مقارنة كل m كلمة في كل موضع، ضع الكلمات في مجموعة تجزئة وابحث فيها عن الأجزاء الأخيرة المحتملة. لا يتجاوز طول أي كلمة L، لذا لا يمكن أن تطابق سوى الأجزاء الـL التي تنتهي عند end. في sunflowerseed، تصبح canEnd صحيحة عند المواضع 0 و3 (sun) و7 (flow) و9 (flower) و13 (seed بعد الموضع 9)، لذا فإن الإجابة هي true. لا يؤدي الموضع 7 إلى نتيجة، لأن أي كلمة لا تبدأ بـer، والجدول لا يأبه بذلك.

هناك n موضعًا، يبحث كل منها في ما لا يزيد عن L جزء، ويتطلب إنشاء الجزء وحسابه بالتجزئة ما يصل إلى L خطوة. وهذا يساوي O(n × L²)، أي بحد أقصى 300 × 20 × 20 = 1.2 × 10^5 خطوة حرفية، مهما كان حجم القاموس. يقرأ إنشاء المجموعة كل كلمة مرة واحدة، أي O(m × L)، لذا فإن التعقيد الكلي هو O(m × L + n × L²). تحتوي المجموعة على الكلمات، أي O(m × L) حرفًا، ويحتوي الجدول على n + 1 قيمة منطقية. لا يوجد استدعاء递归.

الخوارزمية

ضع كل كلمة في مجموعة تجزئة، وسجّل طول أطول كلمة 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.
التحقق فقط من ظهور كل حرف في s في كلمة ما. باستخدام الكلمتين aaaa وaa، يكون طول كل قطعة زوجيًا، لذا لا يمكن تقسيم aaaaaaa، المكوّنة من سبعة أحرف.
تخزين الإجابات true فقط في الذاكرة المؤقتة. فالإجابة true تنهي البحث على أي حال. يتكرر العمل في الفروع false، لذا فإن الذاكرة المؤقتة التي لا تخزنها تظل أسية الزمن.
جعل الجدول أقصر بمُدخل واحد. تشير canEnd[i] إلى الأحرف i الأولى، وكل من 0 وn قيمتان صالحتان، لذا يحتاج الجدول إلى n + 1 من المُدخلات.
المقارنة بعد نهاية s عندما تكون الكلمة أطول مما تبقى، مثل مقارنة الكلمة abc مع ab. تحقق من الأطوال قبل مقارنة الأحرف.
في Lua وR، تبدأ مواضع السلاسل النصية من 1: فالقطعة التي طولها k وتنتهي عند الحرف e تبدأ عند الحرف e-k+1.

أسئلة شائعة4

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

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

لماذا يفشل النهج الجشع في مسألة تقسيم الكلمات؟

تلتزم القاعدة الجشعة بكلمة واحدة ولا تعيد النظر فيها أبدًا. يقسم أسلوب الأطول أولًا carpetal إلى carpet وal، بينما ينجح التقسيم إلى car + petal. يقسم أسلوب الأقصر أولًا sunflowerseed إلى sun + flow ويعلق عند erseed. تحافظ البرمجة الديناميكية على كل موضع يمكن لأي تقسيم الوصول إليه، ولذلك لا تفقد أبدًا الموضع الصحيح.

هل تُعدّ مشكلة Word Break مسألة برمجة ديناميكية أم مسألة رسوم بيانية؟

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

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

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

Python

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

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

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

المتوقع

true

Word Break

الدالة

القيود

أمثلة

تلميحات

الحل

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

الاستدعاء الذاتي باستخدام مذكرة

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

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

أسئلة شائعة4

مسائل مشابهة