I think BFS is not a good solution to this problem.
- You have to remember your path when doing BFS because each letter can be used only once
- It is not constant time when you check whether an adjacent letter is in your path already.
But it is absolutely doable using BFS. You can define a data structure that store your path and use a queue to implement the BFS.
If you use BFS, you have to record the positions visited for each path, which can get Time Limit Exceeded.
you cam simply use a boolean array to remember the path you've traversed, then the adjacent letter can be checked in constant time, the only cost is the O(n^2) space, also you can count the code complexity is more than DFS solution.
The cost for the space is not
O(n^2) because you have to memorize the path for each element in the queue.
Answers you've written is not relevant to this question. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.