15,032,431 members
Articles / General Programming / Algorithms
Technical Blog
Posted 29 Aug 2015

10K views
5 bookmarked

# Graph is everywhere

Rate me:
The traditional way to solve the ZigZag Conversion problem is to either build a 2d table or find a pattern among the index of the letters on the same row. There is also a beautiful solution which builds on top of Breadth First Search. Continue reading..

The traditional way to solve the ZigZag Conversion problem is to either build a 2d table or find a pattern among the index of the letters on the same row. There is also a beautiful solution which builds on top of the BFS(Breadth First Search).

### Problem

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```P   A   H   N
A P L S I I G
Y   I   R```

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

`string convert(string text, int nRows);`

`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.

Make each letter in the string a node in the graph. If we link the nodes following the order in the original string, we actually build a graph. Each node can have at most two neighbors. The order of the letters in the original string is actually result of DFS(Depth First Search) on this graph.

E.g.,  for string “ABCDE”,

```A   E
B D
C```

the resultant graph is as follows. We create some virtual paths between the nodes on the first row and the Root.

The BFS walk produces “AEBDC”, which is exactly what we want.

Just one thing left. What if the node “E” doesn’t exist?  For the last branch (e.g., it’s C->D here), we may need to create a virtual path to connect to the Root as show below.

Here comes the code.

```from collections import deque

class Node:
def __init__(self, value):
self.visited = False
self.value = value
self.neighbors = []

class Solution:
# @param {string} s
# @param {integer} numRows
# @return {string}
def convert(self, s, numRows):
self.__s = s
self.__numRows = numRows
return self.__BFS(self.__buildGraph())

def __connect(self, prev, this):
prev.neighbors.append(this)
this.neighbors.append(prev)

def __buildGraph(self):
'''Build the graph from DFS traversal of the string'''
root = Node('')
prev = None
row = 0
up = True
for i in range(len(self.__s)):
this = Node(self.__s[i])
if prev is not None:
self.__connect(prev, this)
prev = this
# Connect nearest nodes(those on row #0) to the root
if row == 0:
self.__connect(root, this)

if up:
if row < self.__numRows - 1:
row += 1
elif row > 0:
row -= 1
up = False
else:
if row > 0:
row -= 1
elif row < self.__numRows - 1:
row += 1
up = True

# The triky part, for BFS later
# Build a virtual path to connect to the root for the last branch, if not already
if not up and row < self.__numRows - 2:
for i in range(row, -1, -1):
this = Node('')
self.__connect(prev, this)
prev = this
self.__connect(prev, root)

return root

def __BFS(self, root):
'''Breadth First Search gives the desired string'''
work_queue = deque()
root.visited = True
work_queue.append(root)

s = ''
while work_queue:
node = work_queue.popleft()
# No special action for the root as it is an empty string;)
s += node.value
for i in node.neighbors:
if not i.visited:
i.visited = True
work_queue.append(i)
return s```

## Share

Senior software engineer at National Instruments, to implement various Ethernet-based industrial protocols, e.g., EtherCAT. Favorite languages are C/C++ and Python. For fun, I like watching films (sci-fi, motion), walking, and various reading.