Longest Common Prefix
لديك مصفوفة من الكلمات strs. أعد أطول سلسلة تبدأ بها كل كلمة. إذا لم تبدأ جميع الكلمات بالحرف نفسه، فأعد السلسلة الفارغة "". تُعدّ الكلمة بادئةً لنفسها، لذا تكون الكلمة الوحيدة هي الإجابة.
الدالة
- strsstring-array
- الكلمات للمقارنة
- تُرجعstring
- أطول بادئة تشترك فيها جميع الكلمات، أو سلسلة فارغة
القيود
1 ≤ strs.length ≤ 2001 ≤ strs[i].length ≤ 200- تتكوّن كل كلمة من أحرف إنجليزية صغيرة فقط.
أمثلة
- المدخلات
- strs = ["interview", "internet", "interval", "internal"]
- المخرجات
- "inter"
- الشرح
- تبدأ الكلمات الأربع بـ
inter. في الموضع التالي، تحتويinterviewوintervalعلى الحرفv، بينما تحتويinternetوinternalعلى الحرفn، لذا يتوقف البادئة عند هذا الموضع.
- المدخلات
- strs = ["stack", "queue", "heap"]
- المخرجات
- ""
- الشرح
- تبدأ الكلمات بـ
sوqوh. وهي تختلف في الحرف الأول نفسه، لذا لا تشترك في أي بادئة وتكون الإجابة فارغة.
- المدخلات
- strs = ["prefix", "pre", "prepare"]
- المخرجات
- "pre"
- الشرح
preهي أقصر كلمة، والكلمتان الأخريان تبدآن بها، لذا فهي الإجابة كاملةً. لا يمكن أن تكون البادئة المشتركة أطول من أقصر كلمة.
+19 اختبارات مخفية عند الإرسال
سؤال إضافي
لنفترض أن القائمة تظل ثابتة وأن لديك العديد من كلمات الاستعلام. كيف ستجد، لكل استعلام، أطول بادئة يشترك فيها مع كلمة واحدة على الأقل في القائمة، من دون إعادة فحص القائمة في كل مرة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لا يمكن أن تكون الإجابة أطول من أقصر كلمة. ما الشرط الذي يجب أن ينطبق على كل حرف فيها؟
ينتمي الحرف في الموضع
iإلى الإجابة فقط إذا كان لكل كلمة حرف في الموضعiوكانت جميعها متطابقة. تنتهي الإجابة عند أول موضع لا يتحقق فيه ذلك.تحقّق من مواضع الكلمة الأولى من اليسار إلى اليمين. عند كل موضع، افحص كل كلمة أخرى؛ وبمجرد أن تكون إحداها أقصر من اللازم أو تحتوي على حرف مختلف، أَعِد الجزء من الكلمة الأولى الذي يسبق ذلك الموضع.
الحل
لا ينتمي حرف إلى الإجابة إلا إذا كان كلّ لفظ يحتوي على الحرف نفسه في الموضع نفسه، وتنتهي الإجابة عند أول موضع يختلف فيه أي لفظ أو ينفد. تقرأ الطريقتان أدناه الكلمات حرفًا حرفًا؛ ويكمن الاختلاف بينهما في ترتيب قراءتهما. يتوقف المسح بحسب العمود عند أول اختلاف، لذا لا يقرأ أبدًا ما يتجاوز الإجابة وعمودًا واحدًا إضافيًا.
قلّص البادئة كلمةً تلو الأخرى
الفكرة
ابدأ بافتراض أن الكلمة الأولى كاملة هي الإجابة. ثم قارنها بالكلمة الثانية حرفًا حرفًا، واختصرها إلى الجزء المشترك بينهما. قارن ما تبقّى بالكلمة الثالثة، وهكذا. بعد الكلمة الأخيرة، يكون ما تبقّى مشتركًا بينها جميعًا.
هذا صحيح لأن البادئة المشتركة لعدة كلمات هي البادئة المشتركة للكلمتين الأوليين، ثم البادئة المشتركة لتلك النتيجة والكلمة الثالثة، وهكذا: في كل خطوة، لا يمكن إلا الإبقاء عليها كما هي أو تقصيرها. بالنسبة إلى interview، internet، interval، internal، ينتقل الجزء المرشّح من interview إلى inter بعد الكلمة الثانية، ويبقى كما هو بعد ذلك.
تُقارَن كلٌّ من الحروف مرة واحدة على الأكثر، لذا يكون الزمن O(S)، حيث إن S هو العدد الإجمالي للحروف. لا تحتفظ إلا بطول، لا بنسخة. تكمن نقطة الضعف في الترتيب: مع 200 كلمة، طول كل منها 200 حرف، تتطابق أول 199 كلمة، بينما تختلف الكلمة الأخيرة عند حرفها الأول، ستقارن جميع الأحرف الـ200 مع كل واحدة من الكلمات الـ199 الأولى، أي ما يقارب 40,000 مقارنة، قبل أن تختصر الكلمة الأخيرة البادئة إلى لا شيء.
الخوارزمية
- عيّن
prefixLenإلى طولstrs[0]. - لكل كلمة أخرى، احسب عدد الأحرف الأولى التي تشترك فيها مع
strs[0]، بحد أقصىprefixLen. - عيّن
prefixLenإلى ذلك العدد، وتوقف مبكرًا إذا وصل إلى 0. - أعِد الأحرف
prefixLenالأولى منstrs[0].
def longestCommonPrefix(strs):
first = strs[0]
prefix_len = len(first)
for word in strs[1:]:
common = 0
while common < prefix_len and common < len(word) and word[common] == first[common]:
common += 1
prefix_len = common
if prefix_len == 0:
break
return first[:prefix_len]قارن عمودًا بعمود
الفكرة
اقرأ الكلمات كما لو كانت جدولًا، عمودًا واحدًا في كل مرة. يحتوي العمود 0 على الحرف الأول من كل كلمة، والعمود 1 على الحرف الثاني، وهكذا. خذ حرف strs[0] في العمود الحالي وتحقق من أن كل كلمة أخرى تحتوي على الحرف نفسه في ذلك الموضع. عند أول اختلاف في إحدى الكلمات، أو إذا كانت أقصر من أن تحتوي على ذلك العمود أصلًا، تكون الإجابة هي strs[0] حتى ذلك العمود.
الإجابة هي بالضبط سلسلة الأعمدة التي تتفق فيها كل الكلمات، وهذه الحلقة تمر على تلك الأعمدة من اليسار وتتوقف عند أول عمود ينهي هذه السلسلة. إذا لم يُنهِ أي عمود هذه السلسلة، فإن strs[0] نفسها هي الإجابة؛ وعندها تكون أقصر كلمة، أو مساوية لها في الطول.
تقرأ الحلقة عمودًا واحدًا على الأكثر بعد الإجابة، لذا، مع وجود n كلمات وإجابة طولها L، تجري على الأكثر n × (L+1) عملية تحقق، ولا تقرأ أبدًا الحرف نفسه من أي كلمة مرتين، لذا فإن تعقيدها أيضًا O(S). في الحالة أعلاه، حيث تتفق 199 كلمة وتختلف الكلمة الأخيرة عند حرفها الأول، تتوقف بعد العمود الأول: 199 مقارنة بدلًا من قرابة 40,000.
الخوارزمية
- لتكن
firstهيstrs[0]. - لكل عمود
colمن 0 إلى طولfirstناقص واحد، اقرأfirst[col]. - لكل كلمة أخرى، إذا لم يكن بها حرف عند
colأو كان حرفها مختلفًا، فأعِد أولcolحرفًا منfirst. - إذا تطابقت جميع الأعمدة، فأعِد
first.
def longestCommonPrefix(strs):
first = strs[0]
for col in range(len(first)):
for word in strs[1:]:
if col == len(word) or word[col] != first[col]:
return first[:col]
return first
أخطاء شائعة وحالات حدّية
الإجابة قصيرة، وتكمن الأخطاء في نهايتها.
- القراءة بعد نهاية كلمة أقصر. في
prefixوpreوprepare، يوجد العمود 3 فيprefixلكنه غير موجود فيpre؛ تحقّق من الطول قبل قراءة الحرف. - مقارنة الكلمة الأولى والأخيرة فقط بالترتيب المعطى. يتطلب هذا الاختصار ترتيب الكلمات أولًا: في
abcوxbdوabd، تشترك الكلمتان الأولى والأخيرة فيab، لكنxbdيخالف العمود 0، والإجابة فارغة. - إرجاع
nullأو قيمة بديلة عندما لا يوجد أي شيء مشترك. الإجابة هي السلسلة الفارغة. - نسيان أن الكلمة الواحدة هي بادئتها نفسها:
algorithmوحدها تُرجعalgorithm. - إنشاء الإجابة بإضافة حرف واحد في كل مرة إلى سلسلة غير قابلة للتغيير. إذا كان طول الإجابة 200 حرف، فهذا يعني إنشاء 200 نسخة؛ احتفظ بالطول واقطع الكلمة الأولى مرة واحدة في النهاية.
أسئلة شائعة4
ما هو التعقيد الزمني لأطول بادئة مشتركة؟
يعمل كلا المسحين في زمن O(S)، حيث إن S هو العدد الإجمالي للأحرف في جميع الكلمات، ولا يحتاجان إلا إلى ذاكرة إضافية O(1) إلى جانب الإجابة. كما أن المسح العمودي محدود بـ n × (L+1)، حيث إن L هو طول الإجابة، لذا يتوقف مبكرًا عندما تختلف الكلمات بالقرب من بدايتها.
هل يمكنك إيجاد أطول بادئة مشتركة بترتيب الكلمات؟
نعم. بالترتيب الأبجدي، تبدأ كل كلمة تقع بين الكلمة الأولى والأخيرة بما تشتركان فيه هاتان الكلمتان، لذا فإن مقارنة الكلمة الأولى والأخيرة فقط تعطي الإجابة. تقارن عملية الفرز نحو n log n زوجًا من الكلمات، وهذا يتطلب وقتًا أكثر من المرور على البيانات مرة واحدة، لكن الشيفرة قصيرة.
ماذا ينبغي أن تُرجع البادئة المشتركة الأطول عندما لا توجد بادئة مشتركة؟
إنها تُرجع السلسلة الفارغة "". يحدث ذلك بمجرد أن تبدأ كلمتان بحرفين مختلفين، كما في stack وqueue وheap.
أيهما أفضل، المسح الأفقي أم العمودي؟
كلاهما له أسوأ حالة متماثلة، O(S). يُعدّ المسح العمودي، عمودًا تلو الآخر، الخيار الأكثر أمانًا: إذ يتوقف عند أول عمود تختلف فيه أي كلمة، بينما قد يقارن المسح الأفقي بادئة طويلة بالكثير من الكلمات قبل أن تقطعها كلمة متأخرة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def longestCommonPrefix(strs):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
strs = ["interview", "internet", "interval", "internal"]
المتوقع
"inter"