When trying out my first challenge, it is telling me my code is too many lines.
I erased all comments and extra line breaks to get less than 300 lines, and it still complains. What is the line limit?
Word Search II
I got kicked out of an interview because of my solution, so I am trying to benchmark it here against other's solutions. They claimed mine was 25X slower, yet I am using the same algorithm everyone else is in my online search.
If I could even get the same test data and run it in visual studio that would give me a metric.
@ChristopherPisz Ok, that's at least indeed a hard problem. Still, 300 lines seems like a lot. I don't know of a line limit here, sorry. You could find out by submitting an artificially inflated solution of someone else.
And you can probably get the inputs by intentionally returning a wrong result. Then you'll get to see the input and expected output of the test case you failed. To get the k-th test case, you could use someone's accepted solution to solve the first k-1 test cases correctly and then intentionally screw up the k-th test case.
Or you could post your code here. Maybe we can give some better advice then.
I think part of the problem is that I am too used to trying to be OO. As I look at other's solutions, they use global, combine classes and functionality together, use plain arrays, etc.
Maybe I am silly for trying to make these interview type questions as close to what I'd really write on the job.
As far as performance goes, it looks like others did their trei differently. All I had to go on was the wikipedia article which described it as collapsed, where as everyone else gives every node 26 edges.
#include <algorithm>
#include <functional>
#include <set>
#include <sstream>
#include <string>
#include <vector>
//------------------------------------------------------------------------------
class RadixDictionary
{
protected:
struct Node
{
typedef std::set<Node *, std::function<bool(Node *, Node*)> > Children;
Node(const std::string & value)
:
m_value(value)
, m_children(&RadixDictionary::Node::CompareValues)
{
}
~Node()
{
for( auto child : m_children )
{
if( child )
{
delete child;
}
}
}
static bool CompareValues(const Node * lhs, const Node * rhs)
{
return lhs->m_value < rhs->m_value;
}
std::string m_value;
bool m_terminates; // Contains the end of a word entry
Children m_children;
};
Node * m_root;
public:
RadixDictionary(std::vector<std::string>& words)
:
m_root(new Node(""))
{
for( auto word : words )
{
// Word is valid
Insert(word);
}
}
RadixDictionary(const RadixDictionary & rhs) = delete;
RadixDictionary & operator = (const RadixDictionary & rhs) = delete;
~RadixDictionary()
{
delete m_root;
}
void Insert(const std::string & word, Node * node = nullptr)
{
if( !node )
{
node = m_root;
}
// If the node is a leaf, then create a child from the word part
if( node->m_children.empty() )
{
Node * newNode = new Node(word);
newNode->m_terminates = true;
node->m_children.emplace(newNode);
return;
}
// Check if any children contain a prefix of the word part
// or if it is itself a prefix to the wordpart
for( auto child : node->m_children )
{
// Check if the child is the wordPart
if( child->m_value == word )
{
// The word is already part of the dictionary
child->m_terminates = true;
return;
}
// Check if the child is a prefix to the word part
else if( word.compare(0, child->m_value.size(), child->m_value) == 0 )
{
// Pass the word part without the child's value, to be inserted at the child
Insert(word.substr(child->m_value.size()), child);
return;
}
// Check if the wordPart is a prefix of the child
else if( child->m_value.compare(0, word.size(), word) == 0 )
{
// Split the child into a
// the right side - new node containing the child's value not in common with the wordPart
// the left side - change child's value to the wordPart
// Copy all the child's children into the new node's children
// Make the new node a child of the child node
Node * newNode = new Node(child->m_value.substr(word.size()));
newNode->m_children = child->m_children;
newNode->m_terminates = child->m_terminates;
child->m_value = word;
child->m_terminates = true;
child->m_children.clear();
child->m_children.emplace(newNode);
return;
}
// Check if the child and the word part have any beginnings in common
size_t smallestSize = word.size() < child->m_value.size() ? word.size() : child->m_value.size();
size_t lastCommonIndex = std::string::npos;
for( size_t index = 0; index < smallestSize; ++index )
{
if( child->m_value[index] != word[index] )
{
break;
}
lastCommonIndex = index;
}
if( lastCommonIndex != std::string::npos )
{
// They did have beginnings in common
// We've already check if either one is a prefix of the other, so both will have some left overs
// ...therefore the +1 is safe
Node * newNode = new Node(child->m_value.substr(lastCommonIndex + 1));
newNode->m_children = child->m_children;
newNode->m_terminates = child->m_terminates;
child->m_value = word.substr(0, lastCommonIndex + 1);
child->m_terminates = false;
child->m_children.clear();
child->m_children.emplace(newNode);
Insert(word.substr(lastCommonIndex + 1), child);
return;
}
}
// No children nodes were found
// Create a new child node
Node * newNode = new Node(word);
newNode->m_terminates = true;
node->m_children.emplace(newNode);
}
bool Contains(const std::string & word)
{
Node * currentNode = m_root;
std::string wordPart = word;
while( !currentNode->m_children.empty() )
{
// Find the last child of the current node that is less than the wordPart we are looking for
// Do this by getting the one before the first that is greater than
//
// Example:
// If we are seatching for "at" wordpart of the word "meat"
// and the current node had children "at" "be" "poop"
// We are looking for the node that has "at", so we get "be" and subtract one to get "at"
//
// Example:
// If we are searcing for the wordpart that is the word "meat"
// and the current node had children "at" "be" "me" "poop"
// We are looking for the node that has "me", so we get "poop" and subtract one to get "me"
Node::Children::const_iterator itChild =
currentNode->m_children.upper_bound(&Node(wordPart));
if( itChild == currentNode->m_children.begin() )
{
return false;
}
// We have a child node
Node * child = *(--itChild);
// Check if the child is the wordPart
if( child->m_value == wordPart )
{
if( child->m_terminates )
{
return true;
}
else
{
return false;
}
}
// Check if the child is not a prefix to the word part
// Then we know the trei does not contain the word
else if( wordPart.compare(0, child->m_value.size(), child->m_value) != 0 )
{
return false;
}
// Take out the letters in common from our search and start searching from the child
wordPart = wordPart.substr(child->m_value.size());
currentNode = child;
}
return false;
}
bool IsAPrefixOf(const std::string & word)
{
Node * currentNode = m_root;
std::string wordPart = word;
while( !currentNode->m_children.empty() )
{
// Find the last child of the current node that is less than the wordPart we are looking for
// Do this by getting the one before the first that is greater than
Node::Children::const_iterator itChild = std::upper_bound(currentNode->m_children.begin(),
currentNode->m_children.end(), &Node(wordPart), RadixDictionary::Node::CompareValues);
// Check if the wordPart is a prefix of the child
if( itChild != currentNode->m_children.end() &&
(*itChild)->m_value.compare(0, wordPart.size(), wordPart) == 0 )
{
return true;
}
else if( itChild == currentNode->m_children.begin() )
{
return false;
}
// We have a child node
Node * child = *(--itChild);
// Check if the child is the wordPart
if( child->m_value == wordPart )
{
return true;
}
// Check if the wordPart is a prefix of the child
else if( child->m_value.compare(0, wordPart.size(), wordPart) == 0 )
{
return true;
}
// Check if the child is not a prefix of the wordPart
else if( wordPart.compare(0, child->m_value.size(), child->m_value) != 0 )
{
return false;
}
wordPart = wordPart.substr(child->m_value.size());
currentNode = child;
}
return false;
}
};
//------------------------------------------------------------------------------
class Solution
{
public:
std::vector<std::string> findWords(std::vector<std::vector<char>>& board, std::vector<std::string>& words)
{
// Iterate through all possible starting points
for( size_t y = 0; y < m_data.size(); ++y )
{
for( size_t x = 0; x < m_data[0].size(); ++x )
{
std::string word;
bool * visited = new bool[m_data.size() * m_data[0].size()];
std::fill(visited, visited + (m_data.size() * m_data[0].size()), false);
FindWords(x, y, visited, word);
delete[] visited;
}
}
// Save the results
return m_results;
}
//------------------------------------------------------------------------------
void FindWords(const size_t x, const size_t y, bool * visited, std::string & word)
{
// Mark the current node as visited
visited[y * m_data[0].size() + x] = true;
// Append the character at the current node to the word thus far
word += m_data[y][x];
// We will be replacing q with qu when we search the dictionary
std::string searchWord = word;
size_t index = 0;
while( (index = searchWord.find("q", index)) != std::string::npos )
{
searchWord.replace(index, 1, "qu");
index += 2;
}
// Check if the word is in the dictionary
if( m_dictionary.Contains(searchWord) )
{
m_results.emplace_back(searchWord);
}
// Check if the word is at least part of something contained in the dictionary
else if( !m_dictionary.IsAPrefixOf(searchWord) )
{
if( !word.empty() )
{
word.erase(word.end() - 1);
}
visited[y * m_data[0].size() + x] = false;
return;
}
// Continue the search through adjacent nodes
for( int xOffset = -1; xOffset < 2; ++xOffset )
{
for( int yOffset = -1; yOffset < 2; ++yOffset )
{
int nextX = static_cast<int>(x) + xOffset;
int nextY = static_cast<int>(y) + yOffset;
if( nextX >= 0 && nextX < m_data[0].size() &&
nextY >= 0 && nextY < m_data.size() &&
visited[nextY * m_data[0].size() + nextX] == false )
{
FindWords(nextX, nextY, visited, word);
}
}
}
// We hit here as the call stack is unwinding from the deepest part of the path
// Erase the last character of the word, such that the frames preceding us may continue their search to other adjacent nodes
if( !word.empty() )
{
word.erase(word.end() - 1);
}
// Mark the current node as untraveled, such that the frames preceding us may continue their search to other adjacent nodes
visited[y * m_data[0].size() + x] = false;
}
private:
std::vector<std::vector<char>> m_data;
RadixDictionary m_dictionary;
std::vector<std::string> m_results;
};
@StefanPochmann
Seems really silly to restrict it so.
I'd think people would want lots of room to write comments in thier code, so that when other's look up their solutions, they are easier to follow. Especially, when dealing with algorithms.
I'll try to play with the whitespace some more to get it to run. Thanks!
@ChristopherPisz Well your code is really unusually large. I don't think I've ever seen that limit being a problem here. You're also inflating your code at least with that bad habit of putting {
on a separate line :-P