Ttykuu

What does the "3am" section means in manpages?

A known event to a history junkie

Java - What do constructor type arguments mean when placed *before* the type?

Simple image editor tool to draw a simple box/rectangle in an existing image

My boss asked me to take a one-day class, then signs it up as a day off

Greatest common substring

Why are on-board computers allowed to change controls without notifying the pilots?

Golf game boilerplate

Teaching indefinite integrals that require special-casing

The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?

Word describing multiple paths to the same abstract outcome

How can I raise concerns with a new DM about XP splitting?

"lassen" in meaning "sich fassen"

Should a half Jewish man be discouraged from marrying a Jewess?

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

Organic chemistry Iodoform Reaction

Bob has never been a M before

In Star Trek IV, why did the Bounty go back to a time when whales were already rare?

What was required to accept "troll"?

Reply ‘no position’ while the job posting is still there (‘HiWi’ position in Germany)

Visiting the UK as unmarried couple

Invariance of results when scaling explanatory variables in logistic regression, is there a proof?

Is it okay / does it make sense for another player to join a running game of Munchkin?

Perfect riffle shuffles

Find Shortest Word Edit Path in python

Shortest path via two intermediate pointsGoogle FooBar Level 3 - Shortest path to 14 sum challenge (part 2)Shortest path around a set of pointsShortest path challengeShortest path to transform one word into anotherDijkstra finding shortest path satisfying given constraintsFind The Duplicates using binarySearch pythonFind the shortest path between two points in a 2D matrix with obstaclesPython A Star with fewest turns and shortest path variations

0

$begingroup$

Find the Shortest Word Edit Path

I was given this problem from an interview. 
#Given two words source and target, and a list of words words,
#find the length of the shortest series of edits that transforms source to target. 
#Each edit must change exactly one letter at a time, and each 
#intermediate word (and the final target word) must exist in words.

If the task is impossible, return -1.

Examples:

source = "bit", target = "dog" words = ["but", "put", "big", "pot",
"pog", "dog", "lot"]

output: 5 explanation: bit -> but -> put -> pot -> pog -> dog has 5
transitions. source = "no", target = "go" words = ["to"]

output: -1

def one_letter_difference(current_word, next_word):
 count = 0
 for i in range(len(current_word) -1):

 if current_word[i] != next_word[i]:
 count += 1;
 if count == 1:
 return True
 else:
 return False

def shortestWordEditPath(source, target, words):
 """
 @param source: str
 @param target: str
 @param words: str[]
 @return: int

 Input: source = "bit", target = "dog"
 words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

 Output: 5
 explanation: 
 1 -> 1 -> 1 -> 1 -> 1
 (source) bit -> but -> put -> pot -> pog -> dog (target) 
 has minimum of 5 transitions 
 """
 graph = 

 for i in range(-1, len(words)):
 if i == -1:
 current_word = source
 else:
 current_word = words[i]
 graph[current_word] = []
 for word in range(len(words)):
 next_word = words[word]
 if one_letter_difference(current_word, next_word):
 graph[current_word].append(next_word)

 #perform BFS
 queue = collections.deque()
 seen = set() # visited words
 queue.append([source, 1])
 seen.add(source)

 while len(queue) > 0:
 current, distance = queue.popleft()
 if current == target: return distance
 for neighbor in graph[current]:
 if neighbor not in seen:
 queue.append([neighbor, distance +1])
 seen.add(neighbor)
 return -1

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
test = shortestWordEditPath(source, target,words)
print(test)

python interview-questions

share

asked 9 mins ago

NinjaGNinjaG

825632

$endgroup$

add a comment | 

0

$begingroup$

Find the Shortest Word Edit Path

I was given this problem from an interview. 
#Given two words source and target, and a list of words words,
#find the length of the shortest series of edits that transforms source to target. 
#Each edit must change exactly one letter at a time, and each 
#intermediate word (and the final target word) must exist in words.

If the task is impossible, return -1.

Examples:

source = "bit", target = "dog" words = ["but", "put", "big", "pot",
"pog", "dog", "lot"]

output: 5 explanation: bit -> but -> put -> pot -> pog -> dog has 5
transitions. source = "no", target = "go" words = ["to"]

output: -1

def one_letter_difference(current_word, next_word):
 count = 0
 for i in range(len(current_word) -1):

 if current_word[i] != next_word[i]:
 count += 1;
 if count == 1:
 return True
 else:
 return False

def shortestWordEditPath(source, target, words):
 """
 @param source: str
 @param target: str
 @param words: str[]
 @return: int

 Input: source = "bit", target = "dog"
 words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

 Output: 5
 explanation: 
 1 -> 1 -> 1 -> 1 -> 1
 (source) bit -> but -> put -> pot -> pog -> dog (target) 
 has minimum of 5 transitions 
 """
 graph = 

 for i in range(-1, len(words)):
 if i == -1:
 current_word = source
 else:
 current_word = words[i]
 graph[current_word] = []
 for word in range(len(words)):
 next_word = words[word]
 if one_letter_difference(current_word, next_word):
 graph[current_word].append(next_word)

 #perform BFS
 queue = collections.deque()
 seen = set() # visited words
 queue.append([source, 1])
 seen.add(source)

 while len(queue) > 0:
 current, distance = queue.popleft()
 if current == target: return distance
 for neighbor in graph[current]:
 if neighbor not in seen:
 queue.append([neighbor, distance +1])
 seen.add(neighbor)
 return -1

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
test = shortestWordEditPath(source, target,words)
print(test)

python interview-questions

share

asked 9 mins ago

NinjaGNinjaG

825632

$endgroup$

add a comment | 

$begingroup$

Find the Shortest Word Edit Path

I was given this problem from an interview. 
#Given two words source and target, and a list of words words,
#find the length of the shortest series of edits that transforms source to target. 
#Each edit must change exactly one letter at a time, and each 
#intermediate word (and the final target word) must exist in words.

If the task is impossible, return -1.

Examples:

source = "bit", target = "dog" words = ["but", "put", "big", "pot",
"pog", "dog", "lot"]

output: 5 explanation: bit -> but -> put -> pot -> pog -> dog has 5
transitions. source = "no", target = "go" words = ["to"]

output: -1

def one_letter_difference(current_word, next_word):
 count = 0
 for i in range(len(current_word) -1):

 if current_word[i] != next_word[i]:
 count += 1;
 if count == 1:
 return True
 else:
 return False

def shortestWordEditPath(source, target, words):
 """
 @param source: str
 @param target: str
 @param words: str[]
 @return: int

 Input: source = "bit", target = "dog"
 words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

 Output: 5
 explanation: 
 1 -> 1 -> 1 -> 1 -> 1
 (source) bit -> but -> put -> pot -> pog -> dog (target) 
 has minimum of 5 transitions 
 """
 graph = 

 for i in range(-1, len(words)):
 if i == -1:
 current_word = source
 else:
 current_word = words[i]
 graph[current_word] = []
 for word in range(len(words)):
 next_word = words[word]
 if one_letter_difference(current_word, next_word):
 graph[current_word].append(next_word)

 #perform BFS
 queue = collections.deque()
 seen = set() # visited words
 queue.append([source, 1])
 seen.add(source)

 while len(queue) > 0:
 current, distance = queue.popleft()
 if current == target: return distance
 for neighbor in graph[current]:
 if neighbor not in seen:
 queue.append([neighbor, distance +1])
 seen.add(neighbor)
 return -1

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
test = shortestWordEditPath(source, target,words)
print(test)

python interview-questions

share

asked 9 mins ago

NinjaGNinjaG

825632

$endgroup$

I was given this problem from an interview. 
#Given two words source and target, and a list of words words,
#find the length of the shortest series of edits that transforms source to target. 
#Each edit must change exactly one letter at a time, and each 
#intermediate word (and the final target word) must exist in words.

def one_letter_difference(current_word, next_word):
 count = 0
 for i in range(len(current_word) -1):

 if current_word[i] != next_word[i]:
 count += 1;
 if count == 1:
 return True
 else:
 return False

def shortestWordEditPath(source, target, words):
 """
 @param source: str
 @param target: str
 @param words: str[]
 @return: int

 Input: source = "bit", target = "dog"
 words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

 Output: 5
 explanation: 
 1 -> 1 -> 1 -> 1 -> 1
 (source) bit -> but -> put -> pot -> pog -> dog (target) 
 has minimum of 5 transitions 
 """
 graph = 

 for i in range(-1, len(words)):
 if i == -1:
 current_word = source
 else:
 current_word = words[i]
 graph[current_word] = []
 for word in range(len(words)):
 next_word = words[word]
 if one_letter_difference(current_word, next_word):
 graph[current_word].append(next_word)

 #perform BFS
 queue = collections.deque()
 seen = set() # visited words
 queue.append([source, 1])
 seen.add(source)

 while len(queue) > 0:
 current, distance = queue.popleft()
 if current == target: return distance
 for neighbor in graph[current]:
 if neighbor not in seen:
 queue.append([neighbor, distance +1])
 seen.add(neighbor)
 return -1

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
test = shortestWordEditPath(source, target,words)
print(test)

share

asked 9 mins ago

NinjaGNinjaG

825632

share

asked 9 mins ago

NinjaGNinjaG

825632

asked 9 mins ago

NinjaGNinjaG

825632

asked 9 mins ago

NinjaGNinjaG

825632