Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtrie

Implement Trie (Prefix Tree)

Problem (restated)

Implement Trie with insert, search (full word), and startsWith (prefix).

Intuition

Children map/array per node; end-of-word flag.

Approaches

Trie insert/search/startsWith

Tested only

Time O(L) per opSpace O(Σ L)

Idea. walk edges per char; create on insert; search needs end flag.

Walkthrough. insert apple; search apple true; search app false; startsWith app true.

Trade-offs. Array[26] fastest for lowercase; map generalizes.

Solution

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  end = false;
}

export class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, new TrieNode());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  search(word: string): boolean {
    const n = this.walk(word);
    return !!n && n.end;
  }
  startsWith(prefix: string): boolean {
    return !!this.walk(prefix);
  }
  private walk(s: string): TrieNode | null {
    let n = this.root;
    for (const c of s) {
      if (!n.children.has(c)) return null;
      n = n.children.get(c)!;
    }
    return n;
  }
}

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  end = false;
}

export class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, new TrieNode());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  search(word: string): boolean {
    const n = this.walk(word);
    return !!n && n.end;
  }
  startsWith(prefix: string): boolean {
    return !!this.walk(prefix);
  }
  private walk(s: string): TrieNode | null {
    let n = this.root;
    for (const c of s) {
      if (!n.children.has(c)) return null;
      n = n.children.get(c)!;
    }
    return n;
  }
}

Template connection

Trie template skeleton.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?