Publikuar më

Përballja e sfidave të zakonshme që lidhen me tekstin: Historia e TypeScript

Autorët

Repozitori GitHub: https://github.com/ImBIOS/common-char-extractor-ts

Në fushën e intervistave të programimit, sfidat algoritmike shërbejnë jo vetëm si teste të njohurive teknike, por si dritare në aftësinë e zgjidhjes së problemeve të kandidatëve. Një problem i tillë intrigues, i takuar shpesh, rrotullohet rreth manipulimit të tekstit - një aftësi themelore në arsenalin e zhvilluesit. Sot, ne zhytemi në një problem tërheqës: identifikimin e karaktereve të përbashkëta nëpër disa tekste, dhe si e trajtuam zgjidhjen e tij duke përdorur TypeScript.

Sfida e Zbuluar

De tyra në dorë dukej e thjeshtë, por gënjeshtërish komplekse: duke marrë një grup tekstesh, duhet të shkruanim një funksion që nxjerr dhe kthen një grup karakteresh që shfaqen në të njëjtën pozicion në të gjitha tekstet. Për shembull, duke marrë hyrjen ["abcd", "bcd", "cde", "cdef"], rezultati i pritur do të jetë ["c", "d"], duke treguar se 'c' dhe 'd' janë karakteret e përbashkëta të ndara midis të gjitha teksteve në pozicionet përkatëse.

Formimi i Zgjidhjes

Udhëtimi ynë filloi me zgjedhjen e TypeScript për zgjidhjen - një vendim i motivuar nga sistemi i fortë i tipave të TypeScript, duke përmirësuar besueshmërinë e kodit dhe produktivitetin e zhvilluesit. Hapi fillestar përfshinte iterimin mbi çdo karakter të tekstit të parë, duke e përdorur atë si referencë për të krahasuar me karakteret përkatëse në tekstet e mëvonshme.

/**
 * Nxerr dhe kthen një grup karakteresh që shfaqen në të njëjtën pozicion
 * në të gjitha tekstet brenda grupit të hyrjes.
 *
 * @param {string[]} words - Një grup tekstesh që do të analizohen.
 * @returns {string[]} Një grup karakteresh që janë të përbashkëta në të gjitha tekstet e dhëna,
 * duke ruajtur rendin e tyre të paraqitjes në tekstin e parë.
 */
export function extractCommonLetters(words: string[]): string[] {
  if (words.length === 0) {
    return []
  }

  const copiedWords = [...words]
  const result: string[] = []
  const referenceWord = copiedWords[0]

  // Iteroni mbi çdo karakter në fjalën e parë
  for (let i = 0; i < referenceWord.length; i++) {
    const currentChar = referenceWord[i]
    let isCharCommonAcrossWords = true

    // Kontrolloni nëse karakteri aktual ekziston në secilën nga fjalët e tjera
    for (let j = 1; j < copiedWords.length; j++) {
      const word = copiedWords[j]
      const charIndex = word.indexOf(currentChar)

      // Nëse karakteri nuk gjendet, ndaloni dhe vendosni flamurin në false
      if (charIndex === -1) {
        isCharCommonAcrossWords = false
        break
      } else {
        // Hiqni karakterin e gjetur nga fjala për të trajtuar kopjet
        copiedWords[j] = word.slice(0, charIndex) + word.slice(charIndex + 1)
      }
    }

    // Nëse karakteri është i përbashkët në të gjitha fjalët, shtoni atë në rezultat
    if (isCharCommonAcrossWords) {
      result.push(currentChar)
    }
  }

  return result
}

Ky fragment përmbledh esencën e qasjes sonë, duke theksuar lexueshmërinë dhe logjikën e drejtpërdrejtë për të përballuar problemin.

Udhetimi përtej: Testimi i Zgjidhjes

Për të vërtetuar zgjidhjen tonë, përdorëm një grup rasteshesh provash që mbulojnë skenare të ndryshme - nga raste themelore në raste më komplekse që përfshijnë karaktere të veçanta dhe ndjeshmëri ndaj rasteve. Ky testimi i plotë siguroi që algoritmi ynë ishte i fortë dhe i saktë në një gamë të gjerë të hyrjeve.

Analizimi i Kompleksitetit të Hapësirës dhe Kohës

Pas reflektimit, kompleksiteti kohor i zgjidhjes sonë përcaktohet kryesisht nga numri i karaktereve në tekstin e parë (le të shënojmë këtë si N) dhe numri total i teksteve (shënojmë këtë si M). Për çdo karakter në tekstin e parë, ne kontrollojmë ndodhjen e tij në pozicionin përkatës në të gjitha tekstet e tjera, duke çuar në një kompleksitet kohor prej O(N*M).

Kompleksiteti i hapësirës së zgjidhjes sonë është O(N), pasi ruajmë karakteret e përbashkëta në një grup. Në rastin më të keq, ku të gjitha karakteret janë të përbashkëta në të gjitha tekstet, madhësia e këtij grupi do të ishte proporcionale me gjatësinë e tekstit të parë.

Rrugët për Përmirësim

Ndërsa zgjidhja jonë qëndron e efektshme për një numër të moderuar të teksteve dhe karaktereve, gjithmonë ka hapësirë për optimizim. Ja disa strategji për të përmirësuar më tej performancën e saj:

  1. Mbyllja e Hershme: Nëse në çdo moment një karakter nuk përputhet në pozicionin përkatës në të gjitha tekstet, ne mund të ndalemi herët nga cikli, duke kursyer krahasime të panevojshme.

  2. Optimizimi për Tekste të Shkurtër: Duke filluar me tekstin më të shkurtër si referencë mund të zvogëlojë potencialisht numrin e iteracioneve, pasi minimizon numrin maksimal të karaktereve që duhet të kontrollohen.

  3. Përpunimi Paralel: Për grupe të mëdha të të dhënave, përdorimi i teknikave të përpunimit paralel për të krahasuar karakteret nëpër tekste njëkohësisht mund të zvogëlojë ndjeshëm kohën e ekzekutimit.

  4. Teknikat e Hashingut: Përdorimi i një harte hash për të mbajtur gjurmët e pozicioneve dhe ndodhjeve të karaktereve mund të ofrojë një mënyrë më sofistikuar për të identifikuar karakteret e përbashkëta, veçanërisht kur merreni me grupe të gjera të teksteve.

Mendime Përfunduese

Sfida e karaktereve të përbashkëta shërben si një dëshmi e mrekullueshme për elegancën e problemeve të manipulimit të tekstit, duke ftuar zhvilluesit për të zhytur në nuancat e algoritmeve dhe strukturave të të dhënave. Përmes TypeScript, ne jo vetëm që gjetëm një zgjidhje, por gjithashtu përqafuam një udhëtim të qartësisë, sigurisë së tipave dhe zgjidhjes efektive të problemeve.

Ndërsa mbyllim, është e rëndësishme të kujtojmë që udhëtimi përmes sfidave të programimit është po aq i rëndësishëm sa rruga e marrë sa edhe destinacioni i arritur. Çdo problem, duke përfshirë këtë, ofron një mundësi unike për të përmirësuar aftësitë tona, ripërkufizuar qasjet tona dhe, më e rëndësishmja, për të vazhduar të mësojmë.

Diskuto në Twitter

NDAJ