The Longest Word in a Dictionary

Approach1: Brute Force

The brute force approach will use HashSet Data Structure to store the prefixes present in the array. Using HashSet, we can check whether prefixes exist in the array or not.

class Solution {

    public String longestWord(String[] arr) {

      Arrays.sort(arr);

      // To store the prefixes
      HashSet<String> hash = new HashSet();
      // To store the final word in a new variable.
      String res= "";
      for(String str : arr){
          if(str.length() == 1 || hash.contains(str.substring(0, str.length()-1))){
              if(str.length() > res.length())
                    res= str;
              hash.add(str);
          }
      }
      return res;
    }
}

You can also try this code with Online Java Compiler

Run Code

This approach will create a problem: if two strings have almost identical prefixes, they will repeatedly check. It will work multiple times, so our main work will be now to reduce this problem.

Approach2: Efficient

To reduce the repeated search of the same prefix, we will use the Trie Data structure to locate specific keys within a set. 

These keys are often strings, with links between nodes defined not by the entire key but by individual characters.

The Trie is traversed depth-first, following the links between nodes, which represent each character in the key.

Something like this,

Traversal using DFS Algorithm by using travel and change strategy. As soon as we get the longest string, we update that variable.

In Node class, we will create an array containing the characters lexicographically, i.e., the smallest character at the front and the largest character at the end.

We will be traversing in such a way that we get the longest and lexicographically smaller string.

Also see, Euclid GCD Algorithm

Implementation

import java.io.*;
import java.util.*;

public class Main {
  public static class Node {

          // words contains lowercase letters only
Node[] children = new Node[26];
String word;


}

// To insert a word into the Trie
public static void insert(Node curr, String word) {

for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null)
curr.children[c - 'a'] = new Node();
curr = curr.children[c - 'a'];
}
curr.word = word;
}

// To traverse the words character by character using DFS for finding the longest word
public static void dfs(Node node) {
if (node == null)
return;

if (node.word != null) {
if (node.word.length() > result.length())
result = node.word;
else if (node.word.length() == result.length() && node.word.compareTo(result) < 0)
result = node.word;
}

for (Node child : node.children)
if (child != null && child.word != null)
dfs(child);
}
static String result="";
  public static String longestWord(String[] words) {
    Node root=new Node();
    for(String s:words){
        insert(root,s);
    }
    dfs(root);
    return result;

  }

  public static void main(String[] args) throws Exception {
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(read.readLine());

    String[]words = new String[n];

    for (int i = 0; i < n; i++) {
      words[i] = read.readLine();
    }

    String result = longestWord(words);
    System.out.println(result);

  }
}

You can also try this code with Online Java Compiler

Run Code

Output

Analysis Of Complexity

Time Complexity: To solve the efficient approach, the Time complexity is O(number of words * word length).
Space Complexity: The space complexity to solve the efficient approach is O(number of words).

FAQs

1. What is the Time and Space complexity to solve the above approach?
   The time complexity of the efficient approach is O(number of words * word length).
   The space complexity of the efficient approach is O(number of words).
    
2. What is the use of the Trie Data Structure?
   Trie is a search tree to locate specific keys from within a set.

Key Takeaways

In this blog, we covered the following things:

• What the problem statement is about.
• Approach 1 uses HashMap to check the prefixes in the array.
• Approach 2 uses a Trie data structure that follows the DFS traversal technique following the links between the nodes.
  Also check out - Data Dictionary In Software Engineering

You can use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice. It will help you in mastering efficient coding techniques.

Happy Coding!!!