Click here to Skip to main content
15,078,444 members
Articles / General Programming / Algorithms
Technical Blog
Posted 29 Aug 2015


5 bookmarked

Graph is everywhere

Rate me:
Please Sign up or sign in to vote.
5.00/5 (8 votes)
29 Aug 2015CPOL1 min read
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).


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
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".

Breadth First Search

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

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):

    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
               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

     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
     return s


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Eric Z (Jing)
Technical Lead National Instruments
China China
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.

Comments and Discussions

Questioncode unreadable Pin
Mr.PoorEnglish3-Sep-15 19:53
MemberMr.PoorEnglish3-Sep-15 19:53 
AnswerRe: code unreadable Pin
Eric Z (Jing)5-Sep-15 15:15
MemberEric Z (Jing)5-Sep-15 15:15 
AnswerRe: code unreadable Pin
Liju Sankar11-Oct-15 8:36
professionalLiju Sankar11-Oct-15 8:36 
GeneralRe: code unreadable Pin
Eric Z (Jing)12-Oct-15 2:41
MemberEric Z (Jing)12-Oct-15 2:41 
That's a good suggestion;)

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.