Skip to main content

Exhaustive Programming

When the problem has no clever solution that lets you go faster than exponential time.

Strobro

Vertical Way - Backtracking

/**
On every node.
iterate all possible values to add left and right pointer positions:
add left and right
find(left + 1, right - 1)

Base case.
if right < left add to the result.
if left == right

l
0 1 2
[1,0,1]
r
*/
private Map<Character, Character> pairMap = new HashMap<>();
public List<String> findStrobogrammatic(int n) {
pairMap.put('1', '1');
pairMap.put('6', '9'); // different
pairMap.put('8', '8');
pairMap.put('9', '6'); // different
pairMap.put('0', '0');
List<String> result = new ArrayList<>();
List<char[]> interm = new ArrayList<>();
interm.add(new char[n]);
find(0, n - 1, new char[n], result);
return result;
}
private void find(int left, int right, char[] interm, List<String> result) {
//System.out.println(left + ", " + right);
if (right < left) {
result.add(String.valueOf(interm));
return;
}

if (left == right) {
for (Map.Entry<Character, Character> entry : pairMap.entrySet()) {
char curVal = entry.getKey();
if (curVal == '6' || curVal == '9') continue;
interm[left] = curVal;
find(left + 1, right - 1, interm, result);
}
return;
}
for (Map.Entry<Character, Character> entry : pairMap.entrySet()) {

if (left == 0 && entry.getKey() == '0') continue;
interm[left] = entry.getKey(); interm[right] = entry.getValue();
find(left + 1, right - 1, interm, result);
}
}
  • Time complexity: O(5^N * N)
  • Space complexity: O(5^N * N)

Horizontal Way - Recursive

  /**
Base case.
if right < left
return result.
On every node.
if left == right:
do the below logic only to left.
else:

Create new intermediate result copy. (copy)
For every intermediate value in the interm:
for each every possible left and right permutations:
add the permutation to the new intermediate result copy by making a new copy of the permutation. (copy)

send the new intermediate result copy to the next level.

interm: [1,8,1],
[6, ,9], [8, ,8]

0 1 2
l
[6, ,9],
r
newInterm: [1,0,1] [1,1,1], [1,8,1]
*/
Map<Character, Character> pairMap = new HashMap<>();
public List<String> findStrobogrammatic(int n) {
pairMap.put('1', '1');
pairMap.put('6', '9'); // different
pairMap.put('8', '8');
pairMap.put('9', '6'); // different
pairMap.put('0', '0');
List<String> result = new ArrayList<>();
List<char[]> interm = new ArrayList<>();
interm.add(new char[n]);
// TODO
return find(0, n - 1, interm);
}
private List<String> find(int left, int right, List<char[]> interm) {
if (right < left) {
List<String> result = new ArrayList<>();
for (char[] intermVal : interm) {
result.add(String.valueOf(intermVal));
}
return result;
}
List<char[]> newInterm = new ArrayList<>();

for (char[] intermVal : interm) {
for (Map.Entry<Character, Character> entry : pairMap.entrySet()) {
char curKey = entry.getKey(); char curVal = entry.getValue();
if (left == right) {
if (curVal == '6' || curVal == '9') continue;
intermVal[left] = curVal;
} else {
if (left == 0 && curKey == '0') continue;
intermVal[left] = curKey; intermVal[right] = curVal;
}
newInterm.add(Arrays.copyOfRange(intermVal, 0, intermVal.length));
}
}
return find(left + 1, right - 1, newInterm); //
}

Horizontal Way - Level order traversal

TODO