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

Stats

10K views
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).

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

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
B D
C

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

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

graph2

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


License

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

Share

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 

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.