How to break two loops(while and for)

Question

I want to build the function such that:

Given two words, beginWord and endWord, and a wordList of approved words, find the length of the shortest transformation sequence from beginWord to endWord such that:

Only one letter can be changed at a time

Each transformed word must exist in the wordList.

Return the length of the shortest transformation sequence, or 0 if no such transformation sequence exists.

Example:

For beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], the output should be

wordLadder(beginWord, endWord, wordList) = 5

The shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with a length of 5.

My attempt:

from collections import Counter

def wordLadder(beginWord, endWord, wordList):
    count = 0
    if endWord not in wordList:
        raise ValueError("endword is not in wordList")
    while True:
        for i in range(len(wordList)):
            common = Counter(beginWord) & Counter(wordList[i])
            if beginWord == endWord:
                break
            if sum(common.values()) == len(beginWord) - 1:
                beginWord = wordList[i]
                wordList = wordList[i:]
                count +=1
                break
            else:
                break

But I don't know how to break from second loop (while). How can I do this?

There is no double break in Python, but you can `return`, which terminates the function — Chris_Rands, May 03 '17 at 14:29
Possible duplicate of [How to break out of multiple loops in Python?](http://stackoverflow.com/questions/189645/how-to-break-out-of-multiple-loops-in-python) — fafl, May 03 '17 at 14:30
Instead of `while True`, maybe something like `criteria_met = False` and then `while not criteria_met:`. Once you meet some criteria, set `criteria_met = True`? This helps when you're not inside a function and can't use `return` to break out. — roganjosh, May 03 '17 at 14:30
Which of the multiple `break` statements do you want to exit both loops? — martineau, May 03 '17 at 14:55

score 2 · Answer 1 · edited May 03 '17 at 14:34

You can add another if beginWord == endWord: break after your for-loop. If the first break-condition is satisfied, so will the new one be.


    def wordLadder(beginWord, endWord, wordList):
        count = 0
        if endWord not in wordList:
            raise ValueError("endword is not in wordList")

        while True:
            if beginWord == endWord:
                break
            for i in range(len(wordList)):
                common = Counter(beginWord) & Counter(wordList[i])
                if beginWord == endWord:
                    break
                if sum(common.values()) == len(beginWord) - 1:
                    beginWord = wordList[i]
                    wordList = wordList[i:]
                    count +=1
                    break
                else:
                    break

But in your case, return might be simpler.


    def wordLadder(beginWord, endWord, wordList):
        count = 0
        if endWord not in wordList:
            raise ValueError("endword is not in wordList")

        while True:            
            for i in range(len(wordList)):
                common = Counter(beginWord) & Counter(wordList[i])
                if beginWord == endWord:
                    return
                if sum(common.values()) == len(beginWord) - 1:
                    beginWord = wordList[i]
                    wordList = wordList[i:]
                    count +=1
                    break
                else:
                    break

score 1 · Answer 2 · answered May 03 '17 at 15:02

You can get out of nested loops by raising a custom exception. For example:

from collections import Counter

class Stop(Exception): pass

def wordLadder(beginWord, endWord, wordList):
    if endWord not in wordList:
        raise ValueError("endword is not in wordList")

    count = 0
    try:
        while True:
            for i in range(len(wordList)):
                common = Counter(beginWord) & Counter(wordList[i])
                if beginWord == endWord:
                    raise Stop
                if sum(common.values()) == len(beginWord) - 1:
                    beginWord = wordList[i]
                    wordList = wordList[i:]
                    count +=1
                    raise Stop
                else:
                    raise Stop
    except Stop:
        return count

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

print(wordLadder(beginWord, endWord, wordList))

However this will not give you the desired result of 5. It's unclear to me how your function/alogrithm is supposed to accomplish finding the "shortest transformation sequence" as currently written, even with the ability to terminate both of the loops.

@roganjosh: It just depends on ones point of view as what the exception means. In this case it means there's no sense in continuing (_I think_, but don't know, since I don't understand the OP's algorithm). — martineau, May 03 '17 at 15:25
@roganjosh: What do you consider a "standard approach"? Regardless, exceptions are just a way to abort processing—which implies that they're capable of breaking out of nested loops (as well as nested function calls)—and is why this answers the OP's question. Whether that means some process has failed or succeeded is beside the point IMO. — martineau, May 03 '17 at 15:38
That's fair enough. I wasn't arguing that it was wrong, it just seems counterintuitive to me over setting a flag and using a `while` loop until the flag is satisfied. "Standard approach" is wishy-washy, I guess I just mean a generally-used pattern. I'll clean up my comment trail anyway. — roganjosh, May 03 '17 at 16:04

How to break two loops(while and for)

2 Answers2