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هي أقصر كلمة، وتبدأ الكلمتان الأخريان بها، لذا فهي الإجابة كاملة. لا يمكن أن تكون البادئة المشتركة أطول من أقصر كلمة.
سؤال إضافي
افترض أن القائمة تظل ثابتة وتصل كلمات استعلام كثيرة. كيف ستجد أطول بادئة مشتركة لكل كلمة استعلام مع إحدى كلمات القائمة، من دون إعادة فحص القائمة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لا يمكن أن تكون الإجابة أطول من أقصر كلمة. ما الذي يجب أن ينطبق على كل حرف فيها؟
ينتمي حرف في الموضع
iإلى الإجابة فقط إذا كان لكل كلمة حرف في الموضعiوكانت جميعها متطابقة. تنتهي الإجابة عند أول موضع لا يتحقق فيه ذلك.مرّ على مواضع الكلمة الأولى من اليسار إلى اليمين. عند كل موضع، تحقّق من كل كلمة أخرى؛ وبمجرد أن تكون إحداها أقصر من اللازم أو تحتوي على حرف مختلف، أعد الجزء من الكلمة الأولى الذي يسبق ذلك الموضع.
الحل
لا ينتمي الحرف إلى الإجابة إلا إذا احتوت عليه كل كلمة في الموضع نفسه، وتنتهي الإجابة عند أول موضع تختلف فيه إحدى الكلمات أو تنفد حروفها. تقرأ الطريقتان الكلمات حرفًا حرفًا بترتيب مختلف. ويتوقف المسح عموديًا عند أول اختلاف.
قلّص البادئة كلمةً كلمة
الفكرة
افترض أن الكلمة الأولى كاملةً هي الإجابة. اختصرها إلى الجزء المشترك بينها وبين الكلمة الثانية، ثم الثالثة، وهكذا. البادئة المشتركة لعدة كلمات هي البادئة المشتركة للكلمتين الأوليين، ثم لهذه البادئة والكلمة الثالثة: في كل خطوة، لا يمكن إلا الإبقاء عليها أو تقصيرها. في المثال 1، ينتقل المرشح من interview إلى inter بعد الكلمة الثانية، ويظل كما هو.
تُقارَن كلّ حرف مرة واحدة على الأكثر، لذا يكون الزمن O(S) لعدد S من الأحرف إجمالًا. موطن الضعف هو الترتيب: مع 200 كلمة، طول كل منها 200 حرف، حيث تختلف الكلمة الأخيرة فقط عند حرفها الأول، ستجري ما يقارب 40,000 مقارنة قبل أن تختصر الكلمة الأخيرة البادئة إلى لا شيء.
الخوارزمية
- عيّن
prefixLenإلى طولstrs[0]. - لكل كلمة أخرى، احسب عدد الأحرف الأولى المشتركة بينها وبين
strs[0]، بحد أقصىprefixLen. - عيّن
prefixLenإلى ذلك العدد، وتوقّف مبكرًا إذا وصل إلى 0. - أعِد الأحرف الأولى من
strs[0]وعددهاprefixLen.
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]قارن عمودًا بعمود
الفكرة
اقرأ الكلمات كما لو كانت جدولًا، عمودًا واحدًا في كل مرة. خذ الحرف من strs[0] في العمود الحالي، وتحقّق من أن كل كلمة أخرى تحتوي على الحرف نفسه في ذلك الموضع. عند أول اختلاف في إحدى الكلمات، أو إذا كانت أقصر من أن تحتوي على ذلك العمود، تكون الإجابة هي strs[0] حتى ذلك العمود.
الإجابة هي بالضبط تسلسل الأعمدة التي تتطابق فيها جميع الكلمات، وهذه الحلقة تمرّ على هذا التسلسل من اليسار وتتوقف عند موضع الاختلاف. وإذا لم يحدث أي اختلاف، تكون strs[0] هي الإجابة.
مع وجود n كلمة وإجابة طولها L، تُجري الحلقة على الأكثر n × (L+1) عملية تحقّق، وهذا يساوي أيضًا O(S). في الحالة التي يختلف فيها الحرف الأول من الكلمة الأخيرة فقط من بين 200 كلمة، تتوقف بعد 199 مقارنة.
الخوارزمية
- لتكن
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). المسح العمودي هو الخيار الأكثر أمانًا: إذ يتوقف عند أول عمود تختلف فيه أي كلمة، بينما قد يقارن المسح الأفقي بادئة طويلة مع كلمات كثيرة قبل أن تنهيها كلمة متأخرة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def longestCommonPrefix(strs):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
strs = ["interview", "internet", "interval", "internal"]
الإخراج المتوقع
"inter"