Find the longest common prefix using Trie

The problem addressed here is finding the longest common prefix among a set of strings using a Trie data structure. A Trie, also known as a Prefix Tree, is a versatile data structure that is particularly useful for searching strings and efficiently finding common prefixes among them. This article will walk through the process of using a Trie to find the longest common prefix in a collection of strings.

Problem Description

Given a set of strings, the goal is to find the longest common prefix that exists among all these strings. A common prefix is a sequence of characters that appears at the beginning of two or more strings.

Idea to Solve

To solve this problem, we can use a Trie data structure. A Trie is a tree-like data structure that is well-suited for dealing with strings. It organizes strings in a way that makes it efficient to search for common prefixes.

Algorithm

Create a Node class for the Trie, where each node has a boolean attribute end and an array children of size ALPHABETS, representing the possible characters (26 lowercase English letters).
Create a Trie class that has a root node. Implement an insert method in the Trie class to insert a string into the Trie.
For the longest common prefix, traverse the Trie's structure starting from the root. Find the first node that has multiple non-null children, as this indicates the point where the common prefix diverges.
Recursively continue this process, printing the common character and moving to the next level in the Trie, until a point is reached where multiple children exist again.

Pseudocode

class Node:
    end = False
    children = [None, None, ..., None]  # Size: ALPHABETS

class Trie:
    root = Node()

    function insert(text):
        head = root
        for each character in text:
            index = character - 'a'
            if head.children[index] is None:
                head.children[index] = Node()
            head = head.children[index]
        head.end = true

    function longestPrefix(head, same):
        if head is not None:
            Find the first non-null child index, named as 'location'
            Iterate over all children:
                if child is not null and its index is not 'location':
                    set status to False
            if status is True:
                Print character corresponding to 'location'
                Call longestPrefix with head.children[location] and same + 1
            else if status is False and same is 0:
                Print "No Longest Prefix"

matrix = [...]  # The set of strings
obj = Trie()
for each string in matrix:
    obj.insert(string)
obj.longestPrefix(obj.root, 0)

Code Solution

//C++ program
//Find the Longest Common Prefix using Trie

#include<iostream>

#include<string>

#define ALPHABETS 26
using namespace std;
class Node {
  public:
    bool end;
  Node *children[ALPHABETS];
  Node() {
    this->end = false;
    for (int i = 0; i < ALPHABETS; ++i) {
      this->children[i] = NULL;
    }
  }
};
class Trie {
  public:
    Node *root;
  Trie() {
    this->root = new Node();
  }
  void insert(string text) {
    int length = text.size();
    int index = 0;
    Node *head = this->root;
    for (int level = 0; level < length; level++) {
      index = text[level] - 'a';
      if (head->children[index] == NULL) {
        head->children[index] = new Node();
      }
      head = head->children[index];
    }
    if (head != NULL) {
      head->end = true;
    }
  }
  void longestPrefix(Node *head, int same) {
    if (head != NULL) {
      int location = -1;
      bool status = true;
      for (int i = 0; i < ALPHABETS && status; i++) {
        if (head->children[i] != NULL) {
          if (location == -1) {
            location = i;
          }
          if (i != location) {
            status = false;
          }

        }
      }
      if (status == true) {
        cout << ((char)(location + 97));
        this->longestPrefix(head->children[location], same + 1);
      } else if (status == false && same == 0) {
        cout << "No Longest Prefix" << endl;
      }

    }
  }
};
int main() {
  Trie obj;
  //Insert following data
  obj.insert("cool");
  obj.insert("coder");
  obj.insert("confirm");
  obj.insert("cow");

  obj.longestPrefix(obj.root, 0);
  cout << endl;
}

Output

co

/*
  Java program
  Find the Longest Common Prefix using Trie
*/

class Node {
  //Indicates end of string
  public boolean end;

  public Node[] children;

  public Node(int size) {
    end = false;
    children = new Node[size];
  }
}
public class Trie 
{ 
  public int ALPHABETS = 26;
  public Node root; 

  public Trie()
  {
    root = new Node(ALPHABETS);
  }

  public void insert(String text)
  {
    //first get the length of text
    int length = text.length();
    
    //This variable are used to task find the index location of character
    int index = 0;
    
    //get the root node
    Node head = root;

    for (int level = 0; level < length ; level++ )
    {
      //Get the index
      index = text.charAt(level)-'a';

      if(head.children[index] == null)
      {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if(head != null)
    {  
      //indicates end of string
      head.end = true;
    }
  }
  public void longestPrefix(Node head,int same)
  {
    if (head != null) {
      int location = -1;
      boolean status = true;
      for (int i = 0; i < ALPHABETS && status; i++) {
        if (head.children[i] != null) {
          if (location == -1) {
            location = i;
          }
          if (i != location) {
            status = false;
          }

        }
      }
      if (status == true) {
        System.out.print((char)(location+97));
        longestPrefix(head.children[location], same + 1);
      } else if (status == false && same == 0) {
       
        System.out.print("No Longest Prefix");
      }

    }
    
  }
 
  public static void main(String[] args) 
  {
    //Make object
    Trie obj = new Trie();

   
    obj.insert("cool");
    obj.insert("coder");
    obj.insert("confirm");
    obj.insert("cow");
    
    obj.longestPrefix(obj.root,0);
    System.out.println();
  }
}

Output

co

/*
  C# program
  Find the Longest Common Prefix using Trie
*/
using System;
public class Node {
	//Indicates end of string
	public Boolean end;

	public Node[] children;

	public Node(int size) {
		end = false;
		children = new Node[size];
	}
}
public class Trie 
{ 
	public int ALPHABETS = 26;
	public Node root; 

	public Trie()
	{
		root = new Node(ALPHABETS);
	}

	public void insert(String text) {
		//first get the.Length of text
		int size = text.Length;

		//This variable are used to task find the index location of character
		int index = 0;

		//get the root node
		Node head = root;

		for (int level = 0; level < size; level++) {
			//Get the index
			index = text[level] - 'a';

			if (head.children[index] == null) {
				//When need to add new Node
				head.children[index] = new Node(ALPHABETS);
			}

			head = head.children[index];
		}
		if (head != null) {
			//indicates end of string
			head.end = true;
		}
	}
	public void longestPrefix(Node head,int same)
	{
		if (head != null) {
			int location = -1;
			Boolean status = true;
			for (int i = 0; i < ALPHABETS && status; i++) {
				if (head.children[i] != null) {
					if (location == -1) {
						location = i;
					}
					if (i != location) {
						status = false;
					}

				}
			}
			if (status == true) {
				Console.Write((char)(location+97));
				longestPrefix(head.children[location], same + 1);
			} else if (status == false && same == 0) {

				Console.Write("No Longest Prefix");
			}

		}

	}

	public static void Main(String[] args) 
	{
		//Make object
		Trie obj = new Trie();


		obj.insert("cool");
		obj.insert("coder");
		obj.insert("confirm");
		obj.insert("cow");

		obj.longestPrefix(obj.root,0);
		Console.WriteLine();
	}
}

Output

co

# Ruby Program
# Find the Longest Common Prefix using Trie
class Node 
	attr_reader :end, :children
    attr_accessor :end, :children
	def initialize(size) 
		@end = false
		@children = Array.new(size){nil}
	end
end

class Trie 
	attr_reader :ALPHABETS, :root
    attr_accessor :ALPHABETS, :root
	def initialize() 
        @ALPHABETS = 26
		@root = Node.new(@ALPHABETS)
	end
	def insert(text) 
		length = text.length()
		location = 0
		head = @root
		level = 0
		while (level < length) 
			location = text[level].ord - 'a'.ord
			if (head.children[location] == nil) 
				head.children[location] = Node.new(@ALPHABETS)
			end
			head = head.children[location]
			level += 1
		end
		if (head != nil) 
			head.end = true
		end
	end
	def longestPrefix(head, same) 
		if (head != nil) 
			location = -1
			status = true
			i = 0
			while (i < @ALPHABETS and status==true) 
				if (head.children[i] != nil) 
					if (location == -1) 
						location = i
					elsif (i != location) 
						status = false
					end
				end
				i += 1
			end
			if (status == true) 
				print((location + 97).chr)
				self.longestPrefix(head.children[location], same + 1)
			elsif (status == false and same == 0) 
				print("No Longest Prefix")
			end
		end
	end
end
def main() 
	obj = Trie.new()
	obj.insert("cool")
	obj.insert("coder")
	obj.insert("confirm")
	obj.insert("cow")
	obj.longestPrefix(obj.root,0)
	print("\n")
end
main()

Output

co

# Python Program
# Find the Longest Common Prefix using Trie
class Node :

  def __init__(self, size) :
    self.end = False;
    self.children = [None]*size;
  

class Trie :
  

  def __init__(self) :
    self.ALPHABETS = 26;
    self.root = Node(self.ALPHABETS);
  
  def insert(self, text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while (level < length) :
      index = ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        head.children[index] = Node(self.ALPHABETS)
      
      head = head.children[index]
      level += 1
    
    if (head != None) :
      head.end = True
     
  
  def longestPrefix(self, head, same) :
    if (head != None) :
      location = -1;
      status = True;
      i = 0;
      while (i < self.ALPHABETS and status) :
        if (head.children[i] != None) :
          if (location == -1) :
            location = i;
          
          if (i != location) :
            status = False;
          
        
        i += 1;
      
      if (status == True) :
        print(chr(location + 97),end="")
        self.longestPrefix(head.children[location], same + 1);
      elif (status == False and same == 0) :
        print("No Longest Prefix");
    
  
def main() :
  obj = Trie();
  obj.insert("cool");
  obj.insert("coder");
  obj.insert("confirm");
  obj.insert("cow");
  obj.longestPrefix(obj.root,0);
  print();
  

if __name__ == "__main__":
  main()

Output

co

/*
  Node JS Program
  Find the Longest Common Prefix using Trie
*/
class Node {

	constructor(size) {
		this.end = false;
		this.children =  new Array(size).fill(null);
	}
}
class Trie {
	
	constructor() {
		this.ALPHABETS = 26;
		this.root = new Node(this.ALPHABETS);
	}
	insert(text) {
		var length = text.length;
		var index = 0;
		var head = this.root;
		var level = 0;
		while (level < length) {
			index = text.charCodeAt(level) - 'a'.charCodeAt(0);;
			if (head.children[index] == null) {
				head.children[index] = new Node(this.ALPHABETS);
			}
			head = head.children[index];
			level++;
		}
		if (head != null) {
			head.end = true;
		}
	}
	longestPrefix(head, same) {
		if (head != null) {
			var location = -1;
			var status = true;
			var i = 0;
			while (i < this.ALPHABETS && status) {
				if (head.children[i] != null) {
					if (location == -1) {
						location = i;
					}
					if (i != location) {
						status = false;
					}
				}
				i++;
			}
			if (status == true) {
				process.stdout.write(String.fromCharCode(location + 97));
				this.longestPrefix(head.children[location], same + 1);
			} else
			if (status == false && same == 0) {
				process.stdout.write("No Longest Prefix");
			}
		}
	}
}

function main() {
	var obj = new Trie();
	obj.insert("cool");
	obj.insert("coder");
	obj.insert("confirm");
	obj.insert("cow");
	obj.longestPrefix(obj.root,0);
	process.stdout.write("\n");
}
main();

Output

co

<?php
/*
  Php Program
  Find the Longest Common Prefix using Trie
*/
class Node {
  public $end;
  public $children;

  function __construct($size) {
    $this->end = false;
    $this->children = array_fill(0, $size, null);
  }
}
class Trie {
  public $ALPHABETS = 26;
  public $root;

  function __construct() {
    $this->root = new Node($this->ALPHABETS);
  }
  public  function insert($text) {
    $length = strlen($text);
    $index = 0;
    $head = $this->root;
    $level = 0;
    while ($level < $length) {
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        $head->children[$index] = new Node($this->ALPHABETS);
      }
      $head = $head->children[$index];
      $level++;
    }
    if ($head != null) {
      $head->end = true;
    }
  }
  public function longestPrefix($head, $same) {
    if ($head != null) {
      $location = -1;
      $status = true;
      $i = 0;
      while ($i < $this->ALPHABETS && $status) {
        if ($head->children[$i] != null) {
          if ($location == -1) {
            $location = $i;
          }
          if ($i != $location) {
            $status = false;
          }
        }
        $i++;
      }
      if ($status == true) {
        echo(chr($location + 97));
        $this->longestPrefix($head->children[$location], $same + 1);
      } else
      if ($status == false && $same == 0) {
        echo("No Longest Prefix");
      }
    }
  
  }
}
function main() {
    $obj = new Trie();
    $obj->insert("cool");
    $obj->insert("coder");
    $obj->insert("confirm");
    $obj->insert("cow");
    $obj->longestPrefix($obj->root,0);
    echo ("\n");
}
main();

Output

co

Time Complexity

Inserting each string into the Trie takes O(length), where length is the average length of the strings.
Finding the longest common prefix takes O(n), where n is the length of the longest common prefix among the given strings.

Find the longest common prefix using Trie

Problem Description

Idea to Solve

Algorithm

Pseudocode

Code Solution

Output

Output

Output

Output

Output

Output

Output

Time Complexity

Comment

New Comment