LeetCode platformunda yer alan ve yaz\u0131l\u0131m m\u00fclakatlar\u0131nda s\u0131k\u00e7a kar\u015f\u0131la\u015f\u0131lan problemlerden biri olan “14. Longest Common Prefix” (En Uzun Ortak \u00d6nek) problemi, string manip\u00fclasyonu ve temel algoritma bilgisi gerektiren klasik bir sorudur. Bu makalede, bu problemin ne oldu\u011funu, farkl\u0131 \u00e7\u00f6z\u00fcm yakla\u015f\u0131mlar\u0131n\u0131, bu yakla\u015f\u0131mlar\u0131n zaman ve uzay karma\u015f\u0131kl\u0131klar\u0131n\u0131 detayl\u0131 bir \u015fekilde inceleyece\u011fiz. Amac\u0131m\u0131z, hem problemi derinlemesine anlaman\u0131z\u0131 sa\u011flamak hem de m\u00fclakatlarda bu t\u00fcr sorulara nas\u0131l yakla\u015fman\u0131z gerekti\u011fi konusunda size rehberlik etmektir.<\/p>\n
En Uzun Ortak \u00d6nek (Longest Common Prefix – LCP), verilen bir string dizisindeki t\u00fcm stringlerin ortak olarak sahip oldu\u011fu en uzun ba\u015flang\u0131\u00e7 k\u0131sm\u0131d\u0131r. E\u011fer b\u00f6yle bir ortak \u00f6nek yoksa, bo\u015f bir string (“”) d\u00f6nd\u00fcr\u00fclmelidir. Bu problem, veri i\u015fleme, dosya sistemleri, arama motorlar\u0131 ve hatta genetik dizilim analizleri gibi bir\u00e7ok ger\u00e7ek d\u00fcnya uygulamas\u0131nda kar\u015f\u0131m\u0131za \u00e7\u0131kabilir.<\/p>\n
Size bir string dizisi Girdi: Girdi: Girdi: Bu problem, string i\u015fleme yeteneklerinizi, d\u00f6ng\u00fcleri ve ko\u015fullu ifadeleri kullanma becerinizi \u00f6l\u00e7er. M\u00fclakatlarda adaylar\u0131n problem \u00e7\u00f6zme yakla\u015f\u0131mlar\u0131n\u0131, farkl\u0131 algoritmalar\u0131 kar\u015f\u0131la\u015ft\u0131rma yeteneklerini ve kodlama pratiklerini de\u011ferlendirmek i\u00e7in ideal bir sorudur. Ayr\u0131ca, Trie (Prefix Tree) gibi geli\u015fmi\u015f veri yap\u0131lar\u0131na giri\u015f i\u00e7in de iyi bir ba\u015flang\u0131\u00e7 noktas\u0131 olabilir.<\/p>\n Longest Common Prefix problemini \u00e7\u00f6zmek i\u00e7in birden fazla yol bulunmaktad\u0131r. Her bir yakla\u015f\u0131m\u0131n kendine g\u00f6re avantajlar\u0131 ve dezavantajlar\u0131 vard\u0131r. Bu b\u00f6l\u00fcmde, en yayg\u0131n ve etkili y\u00f6ntemlere genel bir bak\u0131\u015f sunaca\u011f\u0131z.<\/p>\n Problemi \u00e7\u00f6zmek i\u00e7in genellikle \u00fc\u00e7 ana kategoriye ayr\u0131lan yakla\u015f\u0131mlar mevcuttur:<\/p>\n Daha karma\u015f\u0131k senaryolarda veya \u00e7ok say\u0131da LCP sorgusu gerekti\u011finde Trie (Prefix Tree) gibi \u00f6zel veri yap\u0131lar\u0131 da kullan\u0131labilir. Ancak bu makalede daha \u00e7ok temel algoritmik yakla\u015f\u0131mlara odaklanaca\u011f\u0131z.<\/p>\n Yatay tarama, LCP problemini \u00e7\u00f6zmek i\u00e7in en sezgisel ve anla\u015f\u0131lmas\u0131 kolay y\u00f6ntemlerden biridir. Bu y\u00f6ntemde, ilk stringi ba\u015flang\u0131\u00e7 \u00f6neki olarak al\u0131r\u0131z ve bu \u00f6neki s\u0131rayla dizideki di\u011fer t\u00fcm stringlerle kar\u015f\u0131la\u015ft\u0131r\u0131r\u0131z. E\u011fer mevcut \u00f6nek, bir sonraki stringin ba\u015flang\u0131c\u0131 de\u011filse, \u00f6neki bir karakter k\u0131salt\u0131r\u0131z ve tekrar deneriz.<\/p>\n Algoritma, ilk stringi potansiyel LCP olarak kabul eder. Daha sonra, bu potansiyel LCP’yi ikinci string ile kar\u015f\u0131la\u015ft\u0131r\u0131r. E\u011fer ikinci string, potansiyel LCP ile ba\u015flam\u0131yorsa, potansiyel LCP’nin son karakterini atar ve bu i\u015flemi ikinci string ile tekrar dener. Bu i\u015flem, potansiyel LCP, ikinci stringin bir \u00f6neki olana kadar devam eder. \u0130kinci string ile ortak \u00f6nek bulunduktan sonra, bu yeni (k\u0131salt\u0131lm\u0131\u015f) \u00f6nek, \u00fc\u00e7\u00fcnc\u00fc string ile ayn\u0131 \u015fekilde kar\u015f\u0131la\u015ft\u0131r\u0131l\u0131r. Bu s\u00fcre\u00e7, dizideki t\u00fcm stringler taranana kadar devam eder.<\/p>\n <\/code><\/p>\n Dikey tarama y\u00f6ntemi, yatay taraman\u0131n aksine, stringleri karakter karakter dikey olarak kar\u015f\u0131la\u015ft\u0131r\u0131r. Bu yakla\u015f\u0131m, genellikle yatay taramadan daha verimli olabilir \u00e7\u00fcnk\u00fc gereksiz substring kopyalama i\u015flemlerinden ka\u00e7\u0131n\u0131r.<\/p>\n Bu y\u00f6ntemde, ilk stringin her karakterini s\u0131rayla ele al\u0131r\u0131z. Her karakter i\u00e7in, dizideki di\u011fer t\u00fcm stringlerin ayn\u0131 pozisyondaki karakterini kontrol ederiz. E\u011fer herhangi bir stringin o pozisyondaki karakteri, ilk stringin karakterinden farkl\u0131ysa veya o stringin uzunlu\u011fu o pozisyona kadar gelmiyorsa (yani daha k\u0131saysa), o noktaya kadar bulunan k\u0131s\u0131m en uzun ortak \u00f6nektir. Bu durumda, ilk stringin o pozisyona kadar olan k\u0131sm\u0131n\u0131 d\u00f6nd\u00fcr\u00fcr\u00fcz.<\/p>\n <\/code><\/p>\n B\u00f6l ve Y\u00f6net (Divide and Conquer), karma\u015f\u0131k bir problemi daha k\u00fc\u00e7\u00fck, benzer alt problemlere b\u00f6lerek ve bu alt problemlerin \u00e7\u00f6z\u00fcmlerini birle\u015ftirerek ana problemi \u00e7\u00f6zme prensibine dayanan g\u00fc\u00e7l\u00fc bir algoritma tasar\u0131m paradigmalar\u0131d\u0131r. LCP problemine de bu yakla\u015f\u0131mla \u00e7\u00f6z\u00fcm getirilebilir.<\/p>\n Bu y\u00f6ntemde, string dizisini \u00f6zyinelemeli olarak ikiye b\u00f6leriz. Her alt dizi i\u00e7in LCP'yi buluruz. Daha sonra, bu iki alt diziden elde edilen LCP'lerin ortak LCP'sini bularak ana problemin \u00e7\u00f6z\u00fcm\u00fcne ula\u015f\u0131r\u0131z. Bu s\u00fcre\u00e7, alt dizide tek bir string kalana kadar devam eder.<\/p>\n Bu yard\u0131mc\u0131 fonksiyon, iki stringi karakter karakter kar\u015f\u0131la\u015ft\u0131r\u0131r ve ilk farkl\u0131 karakteri buldu\u011fu yere kadar olan k\u0131sm\u0131 d\u00f6nd\u00fcr\u00fcr.<\/p>\n <\/code><\/p>\n <\/code><\/p>\n LCP problemini \u00e7\u00f6zmek i\u00e7in yukar\u0131da bahsedilen temel yakla\u015f\u0131mlar\u0131n yan\u0131 s\u0131ra, baz\u0131 \u00f6zel durumlarda veya farkl\u0131 performans gereksinimleri oldu\u011funda kullan\u0131labilecek ba\u015fka y\u00f6ntemler de mevcuttur.<\/p>\n Bu y\u00f6ntem olduk\u00e7a zarif ve \u015fa\u015f\u0131rt\u0131c\u0131 derecede etkilidir. Fikir \u015fudur: E\u011fer bir string dizisini alfabetik olarak s\u0131ralarsak, en uzun ortak \u00f6nek sadece dizinin ilk ve son stringi aras\u0131nda bulunabilir. \u00c7\u00fcnk\u00fc ortak bir \u00f6nek varsa, s\u0131ralama i\u015flemi bu \u00f6neki koruyacakt\u0131r ve bu \u00f6neke sahip t\u00fcm stringler birbirine yak\u0131n konumlanacakt\u0131r. En u\u00e7taki stringler (ilk ve son), ortak \u00f6nekin en k\u0131s\u0131tlay\u0131c\u0131 s\u0131n\u0131rlar\u0131n\u0131 belirleyecektir.<\/p>\n <\/code><\/p>\nstrs<\/code> verilecektir. G\u00f6reviniz, bu dizideki t\u00fcm stringlerin en uzun ortak \u00f6neki olan stringi bulmakt\u0131r. E\u011fer ortak bir \u00f6nek bulunamazsa, bo\u015f bir string \"\"<\/code> d\u00f6nd\u00fcr\u00fcn.<\/p>\n\u00d6rnekler ve A\u00e7\u0131klamalar<\/h4>\n
\n
strs = [\"flower\",\"flow\",\"flight\"]<\/code>
\n \u00c7\u0131kt\u0131: \"fl\"<\/code>
\n A\u00e7\u0131klama: “flower”, “flow” ve “flight” stringlerinin ortak ba\u015flang\u0131\u00e7 k\u0131sm\u0131 “fl”dir. “o” karakteri “flight” stringinde bulunmad\u0131\u011f\u0131 i\u00e7in \u00f6nek “flo” olamaz.<\/p>\nstrs = [\"dog\",\"racecar\",\"car\"]<\/code>
\n \u00c7\u0131kt\u0131: \"\"<\/code>
\n A\u00e7\u0131klama: Verilen stringler aras\u0131nda ortak bir \u00f6nek bulunmamaktad\u0131r.<\/p>\nstrs = [\"apple\",\"apricot\",\"apply\"]<\/code>
\n \u00c7\u0131kt\u0131: \"ap\"<\/code>
\n A\u00e7\u0131klama: \u00dc\u00e7 stringin de “ap” ile ba\u015flad\u0131\u011f\u0131 g\u00f6r\u00fclmektedir.<\/p>\n<\/ul>\nNeden \u00d6nemli?<\/h4>\n
\u00c7\u00f6z\u00fcm Yakla\u015f\u0131mlar\u0131: Genel Bak\u0131\u015f<\/h3>\n
Temel Algoritma Fikirleri<\/h4>\n
\n
Veri Yap\u0131s\u0131 Kullan\u0131m\u0131 (Trie)<\/h4>\n
Yatay Tarama (Horizontal Scanning) Y\u00f6ntemi<\/h3>\n
Y\u00f6ntemin A\u00e7\u0131klamas\u0131<\/h4>\n
Algoritma Ad\u0131mlar\u0131<\/h4>\n
\n
\"\"<\/code> d\u00f6nd\u00fcr.<\/li>\nprefix<\/code> de\u011fi\u015fkenine ata.<\/li>\ns<\/code>) i\u00e7in:\n\n
s<\/code> stringinin prefix<\/code> ile ba\u015flay\u0131p ba\u015flamad\u0131\u011f\u0131n\u0131 kontrol et. (s.startswith(prefix)<\/code> veya s.find(prefix) == 0<\/code>)<\/li>\n\n
prefix<\/code>‘in son karakterini sil (prefix = prefix[:-1]<\/code>).<\/li>\nprefix<\/code> bo\u015f bir string haline gelirse, bu, hi\u00e7bir ortak \u00f6nek olmad\u0131\u011f\u0131 anlam\u0131na gelir. Bu durumda \"\"<\/code> d\u00f6nd\u00fcr ve algoritmay\u0131 sonland\u0131r.<\/li>\nprefix<\/code> de\u011feri t\u00fcm stringlerin ortak \u00f6neki olacakt\u0131r. Bu de\u011feri d\u00f6nd\u00fcr.<\/li>\n<\/ol>\nKod \u00d6rne\u011fi (Python)<\/h4>\n
\ndef longestCommonPrefix_horizontal(strs):\n if not strs:\n return \"\"\n \n # \u0130lk stringi ba\u015flang\u0131\u00e7 \u00f6neki olarak al\n prefix = strs[0]\n \n # \u0130kinci stringden ba\u015flayarak t\u00fcm stringleri gez\n for i in range(1, len(strs)):\n # Mevcut prefix, strs[i]'nin \u00f6neki mi?\n # De\u011filse, prefix'i k\u0131salt\n while strs[i].find(prefix) != 0:\n prefix = prefix[:-1] # Son karakteri sil\n if not prefix: # E\u011fer prefix bo\u015f string olursa, ortak \u00f6nek yok demektir\n return \"\"\n \n return prefix\n\n# \u00d6rnek kullan\u0131m:\nprint(longestCommonPrefix_horizontal([\"flower\",\"flow\",\"flight\"])) # \u00c7\u0131kt\u0131: fl\nprint(longestCommonPrefix_horizontal([\"dog\",\"racecar\",\"car\"])) # \u00c7\u0131kt\u0131:\nprint(longestCommonPrefix_horizontal([\"apple\",\"apricot\",\"apply\"])) # \u00c7\u0131kt\u0131: ap\n<\/pre>\nAvantajlar ve Dezavantajlar<\/h4>\n
\n
\n
\n
find()<\/code> veya startswith()<\/code> gibi string metotlar\u0131n\u0131n ve substring alma i\u015flemlerinin maliyeti, \u00f6zellikle Python gibi dillerde, her d\u00f6ng\u00fcde yeni string objeleri olu\u015fturulmas\u0131na neden olabilir. Bu da performans\u0131 etkileyebilir.<\/li>\nDikey Tarama (Vertical Scanning) Y\u00f6ntemi<\/h3>\n
Y\u00f6ntemin A\u00e7\u0131klamas\u0131<\/h4>\n
Algoritma Ad\u0131mlar\u0131<\/h4>\n
\n
\"\"<\/code> d\u00f6nd\u00fcr.<\/li>\nj<\/code> ile). Bu d\u00f6ng\u00fc, potansiyel LCP'nin uzunlu\u011funu belirler.<\/li>\nj<\/code> indeksi i\u00e7in:\n\n
j<\/code>. karakterini (char = strs[0][j]<\/code>) al.<\/li>\nstrs[i]<\/code>) \u00fczerinde bir i\u00e7 d\u00f6ng\u00fc ba\u015flat.<\/li>\nstrs[i]<\/code> stringi i\u00e7in:\n\n
j<\/code>, strs[i]<\/code>'nin uzunlu\u011funa e\u015fitse (yani strs[i]<\/code> daha k\u0131saysa ve j<\/code> indeksine kadar gelmiyorsa) VEYA strs[i][j]<\/code> karakteri char<\/code>'dan farkl\u0131ysa:\n\n
j<\/code> indeksinden \u00f6nce bitti\u011fi anlam\u0131na gelir. \u0130lk stringin 0<\/code>'dan j<\/code>'ye kadar olan k\u0131sm\u0131n\u0131 (strs[0][:j]<\/code>) d\u00f6nd\u00fcr.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\nstrs[0]<\/code>) d\u00f6nd\u00fcr.<\/li>\n<\/ol>\nKod \u00d6rne\u011fi (Python)<\/h4>\n
\ndef longestCommonPrefix_vertical(strs):\n if not strs:\n return \"\"\n \n # \u0130lk stringin karakterleri \u00fczerinde d\u00f6ng\u00fc yap\n for j in range(len(strs[0])): # j, karakter indeksini temsil eder\n char = strs[0][j] # \u0130lk stringin j. karakteri\n \n # Di\u011fer stringleri gez\n for i in range(1, len(strs)): # i, string dizisindeki string indeksini temsil eder\n # E\u011fer mevcut string j indeksine kadar gelmiyorsa (daha k\u0131saysa)\n # veya j. karakter ilk stringin j. karakteriyle e\u015fle\u015fmiyorsa\n if j == len(strs[i]) or strs[i][j] != char:\n # O zaman ortak \u00f6nek 0'dan j'ye kadar olan k\u0131s\u0131md\u0131r\n return strs[0][:j]\n \n # E\u011fer t\u00fcm karakterler e\u015fle\u015ftiyse, ilk stringin tamam\u0131 ortakt\u0131r\n return strs[0]\n\n# \u00d6rnek kullan\u0131m:\nprint(longestCommonPrefix_vertical([\"flower\",\"flow\",\"flight\"])) # \u00c7\u0131kt\u0131: fl\nprint(longestCommonPrefix_vertical([\"dog\",\"racecar\",\"car\"])) # \u00c7\u0131kt\u0131:\nprint(longestCommonPrefix_vertical([\"apple\",\"apricot\",\"apply\"])) # \u00c7\u0131kt\u0131: ap\n<\/pre>\nAvantajlar ve Dezavantajlar<\/h4>\n
\n
\n
\n
B\u00f6l ve Y\u00f6net (Divide and Conquer) Yakla\u015f\u0131m\u0131<\/h3>\n
Y\u00f6ntemin A\u00e7\u0131klamas\u0131<\/h4>\n
Algoritma Ad\u0131mlar\u0131<\/h4>\n
\n
mid = (sol + sag) \/\/ 2<\/code>).<\/li>\n\n
lcp_sol = divide_conquer_helper(strs, sol, mid)<\/code>).<\/li>\nlcp_sag = divide_conquer_helper(strs, mid + 1, sag)<\/code>).<\/li>\n<\/ol>\n<\/li>\nlcp_sol<\/code> ve lcp_sag<\/code> stringlerinin en uzun ortak \u00f6nekini bulan yard\u0131mc\u0131 bir fonksiyon (\u00f6rne\u011fin find_common_between_two(s1, s2)<\/code>) kullanarak sonucu birle\u015ftir.<\/li>\n<\/ol>\nYard\u0131mc\u0131 Fonksiyon: \u0130ki String Aras\u0131ndaki LCP'yi Bulma<\/h4>\n
\ndef find_common_between_two(s1, s2):\n min_len = min(len(s1), len(s2))\n for i in range(min_len):\n if s1[i] != s2[i]:\n return s1[:i]\n return s1[:min_len] # E\u011fer bir fark bulunamazsa, daha k\u0131sa olan stringin tamam\u0131 ortakt\u0131r\n<\/pre>\nKod \u00d6rne\u011fi (Python)<\/h4>\n
\ndef longestCommonPrefix_divide_conquer(strs):\n if not strs:\n return \"\"\n return divide_conquer_helper(strs, 0, len(strs) - 1)\n\ndef divide_conquer_helper(strs, left, right):\n if left == right: # Temel durum: tek bir string\n return strs[left]\n \n mid = (left + right) \/\/ 2\n lcp_left = divide_conquer_helper(strs, left, mid) # Sol yar\u0131 i\u00e7in LCP'yi bul\n lcp_right = divide_conquer_helper(strs, mid + 1, right) # Sa\u011f yar\u0131 i\u00e7in LCP'yi bul\n \n return find_common_between_two(lcp_left, lcp_right) # \u0130ki LCP'nin ortak \u00f6nekini bul\n\n# \u00d6rnek kullan\u0131m:\nprint(longestCommonPrefix_divide_conquer([\"flower\",\"flow\",\"flight\"])) # \u00c7\u0131kt\u0131: fl\nprint(longestCommonPrefix_divide_conquer([\"dog\",\"racecar\",\"car\"])) # \u00c7\u0131kt\u0131:\nprint(longestCommonPrefix_divide_conquer([\"apple\",\"apricot\",\"apply\"])) # \u00c7\u0131kt\u0131: ap\n<\/pre>\nAvantajlar ve Dezavantajlar<\/h4>\n
\n
\n
\n
Di\u011fer Yakla\u015f\u0131mlar ve Veri Yap\u0131lar\u0131<\/h3>\n
S\u0131ralama (Sorting) Yakla\u015f\u0131m\u0131<\/h4>\n
Algoritma Ad\u0131mlar\u0131<\/h5>\n
\n
\"\"<\/code> d\u00f6nd\u00fcr.<\/li>\nfirst<\/code>) ve son stringini (last<\/code>) al.<\/li>\nfirst<\/code> ve last<\/code> stringlerini karakter karakter kar\u015f\u0131la\u015ft\u0131r. \u0130lk farkl\u0131 karakteri buldu\u011fun yere kadar olan k\u0131s\u0131m LCP'dir.<\/li>\nKod \u00d6rne\u011fi (Python)<\/h5>\n
\ndef longestCommonPrefix_sorting(strs):\n if not strs:\n return \"\"\n \n strs.sort() # String dizisini alfabetik olarak s\u0131rala\n \n first = strs[0]\n last = strs[-1]\n \n i = 0\n # \u0130lk ve son stringin karakterlerini kar\u015f\u0131la\u015ft\u0131r\n while i < len(first) and i < len(last) and first[i] == last[i]:\n i += 1\n \n return first[:i] # Ortak olan k\u0131sm\u0131 d\u00f6nd\u00fcr\n\n# \u00d6rnek kullan\u0131m:\nprint(longestCommonPrefix_sorting([\"flower\",\"flow\",\"flight\"])) # \u00c7\u0131kt\u0131: fl\nprint(longestCommonPrefix_sorting([\"dog\",\"racecar\",\"car\"])) # \u00c7\u0131kt\u0131:\nprint(longestCommonPrefix_sorting([\"apple\",\"apricot\",\"apply\"])) # \u00c7\u0131kt\u0131: ap\n<\/pre>\nAvantajlar ve Dezavantajlar<\/h5>\n
\n
\n