# Solution that doesn't use recursive calls

• 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]) {
}
}
}
}

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;
}
}
}
};
```

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