Задача · строки сложная Python ·

Word ladder

def ladder_length(begin: str, end: str, words: list[str]) -> int:

ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])  # -> 5
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])  # -> 0

• 1-е местоGoogle Gemini 3.8 Flashрешено · 10 из 10 тестовответ за 3.1 с · работа 32 мс · $0.0014

  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])ожидалось 5	1 мс
  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])ожидалось 0	<1 мс

  ✓ 1 мс✓ 1 мс✓ <1 мс✓ 1 мс✓ 1 мс✓ 1 мс⏱ 9 мс⏱ 13 мс
  Код

  def ladder_length(begin: str, end: str, words: list[str]) -> int:
      if begin == end:
          return 1
      
      word_set = set(words)
      if end not in word_set:
          return 0
      
      if begin in word_set:
          word_set.remove(begin)
          
      front = {begin}
      back = {end}
      word_set.discard(end)
      
      length = 1
      word_len = len(begin)
      alphabet = 'abcdefghijklmnopqrstuvwxyz'
      
      while front and back:
          if len(front) > len(back):
              front, back = back, front
              
          next_front = set()
          for word in front:
              for i in range(word_len):
                  orig_char = word[i]
                  for c in alphabet:
                      if c == orig_char:
                          continue
                      nxt = word[:i] + c + word[i+1:]
                      if nxt in back:
                          return length + 1
                      if nxt in word_set:
                          next_front.add(nxt)
                          word_set.remove(nxt)
                          
          length += 1
          front = next_front
          
      return 0

• 2-е местоDeepSeek V4 Pro 0423решено · 10 из 10 тестовответ за 5.1 с · работа 213 мс · $0.0016

  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])ожидалось 5	<1 мс
  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])ожидалось 0	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 96 мс⏱ 111 мс
  Код

  from collections import deque
  
  def ladder_length(begin: str, end: str, words: list[str]) -> int:
      if begin == end:
          return 1
  
      word_set = set(words)
      if end not in word_set:
          return 0
  
      # Preprocess words into a pattern-based adjacency to speed up neighbor lookup
      # For each word, generate all patterns by replacing each character with '*'
      # Map pattern to list of words that match it
      L = len(begin)
      pattern_map = {}
      for word in word_set:
          for i in range(L):
              pattern = word[:i] + '*' + word[i+1:]
              pattern_map.setdefault(pattern, []).append(word)
      # Also add begin to the pattern map, but only for neighbor generation
      for i in range(L):
          pattern = begin[:i] + '*' + begin[i+1:]
          pattern_map.setdefault(pattern, []).append(begin)
  
      # BFS from begin
      queue = deque()
      queue.append((begin, 1))
      visited = set()
      visited.add(begin)
  
      while queue:
          current, dist = queue.popleft()
          for i in range(L):
              pattern = current[:i] + '*' + current[i+1:]
              for neighbor in pattern_map.get(pattern, []):
                  if neighbor == end:
                      return dist + 1
                  if neighbor not in visited:
                      visited.add(neighbor)
                      queue.append((neighbor, dist + 1))
              # Clear pattern to avoid redundant lookups
              pattern_map[pattern] = []
  
      return 0

• 2-е местоOpenAI GPT-6 Lunaрешено · 10 из 10 тестовответ за 2.2 с · работа 215 мс · $0.0001

  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])ожидалось 5	<1 мс
  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])ожидалось 0	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс⏱ 106 мс⏱ 103 мс
  Код

  from collections import defaultdict, deque
  
  def ladder_length(begin: str, end: str, words: list[str]) -> int:
      if begin == end:
          return 1
  
      word_set = set(words)
      if end not in word_set:
          return 0
  
      word_set.add(begin)
      buckets = defaultdict(list)
      length = len(begin)
  
      for word in word_set:
          for i in range(length):
              buckets[word[:i] + "*" + word[i + 1:]].append(word)
  
      queue = deque([(begin, 1)])
      visited = {begin}
  
      while queue:
          word, distance = queue.popleft()
          for i in range(length):
              pattern = word[:i] + "*" + word[i + 1:]
              for neighbor in buckets[pattern]:
                  if neighbor == end:
                      return distance + 1
                  if neighbor not in visited:
                      visited.add(neighbor)
                      queue.append((neighbor, distance + 1))
              buckets[pattern] = []
  
      return 0

• 4-е местоQwen3 Coder Nextрешено · 10 из 10 тестовответ за 3.4 с · работа 585 мс · $0.0002

  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])ожидалось 5	<1 мс
  ✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])ожидалось 0	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ <1 мс⏱ 173 мс⏱ 405 мс
  Код

  from collections import deque
  
  def ladder_length(begin: str, end: str, words: list[str]) -> int:
      # If begin equals end, return 1
      if begin == end:
          return 1
      
      # Convert words to a set for O(1) lookups
      word_set = set(words)
      
      # If end is not in words, no valid sequence exists
      if end not in word_set:
          return 0
      
      # BFS setup
      queue = deque([(begin, 1)])
      visited = {begin}
      
      # Generate all possible next words by changing one letter at a time
      while queue:
          current_word, length = queue.popleft()
          
          # Try changing each position in the word
          for i in range(len(current_word)):
              for c in 'abcdefghijklmnopqrstuvwxyz':
                  if c == current_word[i]:
                      continue
                  
                  new_word = current_word[:i] + c + current_word[i+1:]
                  
                  if new_word == end:
                      return length + 1
                  
                  if new_word in word_set and new_word not in visited:
                      visited.add(new_word)
                      queue.append((new_word, length + 1))
      
      return 0

Стоимость токенов: $0.0034 · Как проходят и оцениваются раунды →