Solution that doesn't use recursive calls


  • 1
    Y

    Explanation of this Algorithm

    • Initial thought.
      Let the original string's characters be the column headers of a 2D vector, and the candidate string's characters be the row headers of a 2D vector. If an element's column header is equal to row header, its value is 1, otherwise it is 0. Now if a non-empty element's diagonal neighbor is also 1, then they are linked into one group. Now this group can be expanded to connect other elements and groups, and it can also be flipped to do so. At the end, if there is such a group that becomes a diagonal line of the entire 2D vector, the 2 stirngs are each other's scrambled one.

    • More thought.
      Instead of connecting a group of 1's as a diagonal line and flip it, we can think a group is a square. So the algorithm will be keeping merging 2 squares that touch at one and only one corner, until there is one that covers the whole area.

    • Tricky thing.
      If the strings are are expected to have duplicate characters, a square may be connected to multiple other squares. So we can't discard squares that are merged into others.

    • | great |
      r | 01000
      g | 10000
      t | 00001
      e | 00100
      a | 00010

    11000
    11000
    00001
    00110
    00110

    11000
    11000
    00111
    00111
    00111

    
    class Solution {
    public:
    	bool isScramble(std::string s1, std::string s2) {
    		if (s1.length() != s2.length()) {
    			return false;
    		}
    		if (!std::is_permutation(s1.begin(), s1.end(), s2.begin())) {
    			return false;
    		}
    		if (s1.length() <= 3) {
    			return true;
    		}
    
    		initializeSquares(s1, s2);
    
    		return expandSquares(1);
    	}
    
    private:
    	struct Square
    	{
    		Square() {}
    		Square(int l, int t, int s) : left(l), top(t), size(s) { }
    		int left;
    		int top;
    		int size;
    	};
    
    	struct SquareLessThanBySize
    	{
    		bool operator()(const Square& s1, const Square& s2) const
    		{
    			return s1.size > s2.size;
    		}
    	};
    
    	using SquareSizes = std::set<int /* size */>; 
    	using Row = std::vector<SquareSizes>;
    
    	int m_length;
    	std::vector<Row> m_rowsBL;
    	std::vector<Row> m_rowsBR;
    	std::vector<Row> m_rowsTL;
    	std::vector<Row> m_rowsTR;
    	std::priority_queue<Square, std::vector<Square>, SquareLessThanBySize> m_squaresToExpand;
    	bool m_found = false;
    
    	bool addSquare(int left, int top, int size)
    	{
    		if (!m_rowsTL[top][left].emplace(size).second) {
    			return false;
    		}
    
    		int right = left + size - 1;
    		int bottom = top + size - 1;
    		m_rowsTR[top][right].emplace(size);
    		m_rowsBL[bottom][left].emplace(size);
    		m_rowsBR[bottom][right].emplace(size);
    		m_squaresToExpand.emplace(left, top, size);
    		return true;
    	}
    
    	void initializeSquares(const std::string s1, std::string s2) {
    		m_found = false;
    		m_length = s1.length();
    		m_rowsBL.assign(m_length, Row(m_length));
    		m_rowsBR.assign(m_length, Row(m_length));
    		m_rowsTL.assign(m_length, Row(m_length));
    		m_rowsTR.assign(m_length, Row(m_length));
    		for (int y = 0; y < m_length; ++y) {
    			auto c2 = s2[y];
    			for (int x = 0; x < m_length; ++x) {
    				if (c2 == s1[x]) {
    					addSquare(x, y, 1);
    				}
    			}
    		}
    	}
    
    	bool expandSquares(int row)
    	{
    		while (!m_squaresToExpand.empty() && !m_found) {
    			auto sq = m_squaresToExpand.top();
    			m_squaresToExpand.pop();
    			expandSquare(sq.left, sq.top, sq.size);
    		}
    
    		return m_found;
    	}
    
    	void expandSquare(int left, int top, int size)
    	{
    		std::vector<Square> newSquares;
    		
    		auto right = left + size;
    		auto bottom = top + size;
    
    		if (top) {
    			// Find in the top-left direction.
    			if (left) {
    				const auto& squares = m_rowsBR[top - 1][left - 1];
    				for (auto size2 : squares) {
    					newSquares.emplace_back(left - size2, top - size2, size + size2);
    				}
    			}
    			// Find in the top-right direction.
    			if (right < m_length) {
    				const auto& squares = m_rowsBL[top - 1][right];
    				for (auto size2 : squares) {
    					newSquares.emplace_back(left, top - size2, size + size2);
    				}
    			}
    		}
    
    		if (bottom < m_length) {
    			// Find in the bottom-left direction.
    			if (left) {
    				const auto& squares = m_rowsTR[bottom][left - 1];
    				for (auto size2 : squares) {
    					newSquares.emplace_back(left - size2, top, size + size2);
    				}
    			}
    			// Find in the bottom-right direction.
    			if (right < m_length) {
    				const auto& squares = m_rowsTL[bottom][right];
    				for (auto size2 : squares) {
    					newSquares.emplace_back(left, top, size + size2);
    				}
    			}
    		}
    
    		for (const auto& sq : newSquares) {
    			if (sq.size == m_length) {
    				m_found = true;
    				return;
    			}
    			addSquare(sq.left, sq.top, sq.size);
    		}
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.