Tries

PHOTO

Tue Jan 17 2023 19:32:57 GMT+0000 (Coordinated Universal Time)

Saved by @Beluga #java

public class Tries {
    static class Node {
        Node[] children = new Node[26];
        boolean endOfWord = false;

        Node() {
            for (int i = 0; i < 26; i++) children[i] = null;
        }
    }

    public static Node root = new Node();

    public static void insert(String word) {
        Node curr = root;
        for (int level = 0; level < word.length(); level++) {
            int idx = word.charAt(level) - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new Node();
            }
            curr = curr.children[idx];
        }
        curr.endOfWord = true;
    }

    public static boolean search(String key) {
        Node curr = root;
        for (int i = 0; i < key.length(); i++) {
            int idx = key.charAt(i) - 'a';
            if (curr.children[idx] == null) return false;
            curr = curr.children[idx];
        }
        return curr.endOfWord;
    }

    public static boolean stringBreak(String key) {
        if(key.length()==0) return true;
        for (int i = 1; i <= key.length(); i++) {
            String word1=key.substring(0,i);
            String word2=key.substring(i);
            if(search(word1) && stringBreak(word2)){
                return true;
            }
        }
        return false;
    }


    public static int countSubstrings(String word){
        for(int i=0;i<word.length();i++){
            insert(word.substring(i));
        }
        return countNodes(root);
    }
    public static int countNodes(Node root){
        if(root==null) return 0;
        int count=0;
        for(int i=0;i<26;i++){
            if(root.children[i]!=null){
                count+=countNodes(root.children[i]);
            }
        }
        return count+1;
    }

    public static String longestWord(String[] words){
        String str="";
        for (String word : words) insert(word);

        return str;
    }
    public static boolean isPresent(String word){
        for()
    }



    public static void main(String[] args) {
        String[] words = {"the", "there", "a", "any", "their", "i", "sam", "samsung","like"};
//        for (String word : words) {
//            insert(word);
//        }

    }
}

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

JAVA Codes

@Beluga

Sudoku Solver N queens- placing n queens in n*n chess board to find all subsets of a string. to find all permutations of a string Linked List + Check Palindrome Keypad combination Stock span parenthesis in stack Area of histogram fractional knapsack chocola greedy Split array largest sum Trees BST Tries Tries prefix prblm 0-1 knapsack

#java #howto #interviewquestions #mobile

How to use Java Swing to create a button

import javax.swing.*;  
public class FirstSwingExample {  
public static void main(String[] args) {  
JFrame f=new JFrame();//creating instance of JFrame  
          
JButton b=new JButton("click");//creating instance of JButton  
b.setBounds(130,100,100, 40);//x axis, y axis, width, height  
          
f.add(b);//adding button in JFrame  
          
f.setSize(400,500);//400 width and 500 height  
f.setLayout(null);//using no layout managers  
f.setVisible(true);//making the frame visible  
}  
}

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting

Rope Cutting Problem

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

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}

#java #interviewquestions #search

How to binary search in Java

import java.util.Stack;

/**
 * Java Program to implement a binary search tree. A binary search tree is a
 * sorted binary tree, where value of a node is greater than or equal to its
 * left the child and less than or equal to its right child.
 * 
 * @author WINDOWS 8
 *
 */
public class BST {

    private static class Node {
        private int data;
        private Node left, right;

        public Node(int value) {
            data = value;
            left = right = null;
        }
    }

    private Node root;

    public BST() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * Java function to check if binary tree is empty or not
     * Time Complexity of this solution is constant O(1) for
     * best, average and worst case. 
     * 
     * @return true if binary search tree is empty
     */
    public boolean isEmpty() {
        return null == root;
    }

    
    /**
     * Java function to return number of nodes in this binary search tree.
     * Time complexity of this method is O(n)
     * @return size of this binary search tree
     */
    public int size() {
        Node current = root;
        int size = 0;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                size++;
                current = stack.pop();
                current = current.right;
            }
        }
        return size;
    }


    /**
     * Java function to clear the binary search tree.
     * Time complexity of this method is O(1)
     */
    public void clear() {
        root = null;
    }

}

#java #java #arraylists #while-loops #equala

How to insert ArrayList into While-condition?

List<String> songList = new ArrayList<>();
songList.add("Some song"); //Repeat until satisfied

System.out.println("\n\tWelcome! Please choose a song!");
String songChoice = scan.nextLine();
while (!songList.contains(songChoice)) {
    //Do stuff when input is not a recognised song
}

#java #gfg #geeksforgeeks #arrays #practice #frequencycount #frequencies #limitedrange

Frequencies of Limited Range Array Elements

class Solution{
    //Function to count the frequency of all elements from 1 to N in the array.
    public static void frequencyCount(int arr[], int N, int P)
    {
        //Decreasing all elements by 1 so that the elements
        //become in range from 0 to n-1.
        int maxi = Math.max(P,N);
        int count[] = new int[maxi+1];
        Arrays.fill(count, 0);
        for(int i=0;i<N;i++){
            count[arr[i]]++; 
        }
        
        for(int i=0;i<N;i++){
            arr[i] = count[i+1];
        }
    }
}

How to efficiently iterate over each entry in a Java Map

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

Print Nested Array in Java

String[][] deepArray = new String[][] {{"John", "Mary"}, {"Alice", "Bob"}};
System.out.println(Arrays.toString(deepArray));
//output: [[Ljava.lang.String;@106d69c, [Ljava.lang.String;@52e922]
System.out.println(Arrays.deepToString(deepArray));

#java #java #2dchar array

How do you check a row in a 2D char array for a specific element and then count how many of that element are in the row? (Java)

private boolean oneQueenPerRow() {
    int foundQueens;
    for (int i = 0; i < board.length; i++) {
        foundQueens = 0;//each loop is a checked row
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == QUEEN)
                foundQueens++;
        }
        if (foundQueens > 1) return false;
    }
    return true;
}

#java #logic #algorithms #interesting #arrays

Flood Fill Algorithm: Like the bucket tool in Paint app but for multi-dimensional arrays

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

class Pair {
    int x, y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class FloodFill
{
    // Below arrays details all 8 possible movements
    private static final int[] row = { -1, -1, -1, 0, 0, 1, 1, 1 };
    private static final int[] col = { -1, 0, 1, -1, 1, -1, 0, 1 };

    // check if it is possible to go to pixel (x, y) from
    // current pixel. The function returns false if the pixel
    // has different color or it is not a valid pixel
    public static boolean isSafe(char[][] M, int m, int n,
                                int x, int y, char target)
    {
        return x >= 0 && x < m && y >= 0 && y < n
                && M[x][y] == target;
    }

    // Flood fill using BFS
    public static void floodfill(char[][] M, int x, int y, char replacement)
    {
        int m = M.length;
        int n = M[0].length;

        // create a queue and enqueue starting pixel
        Queue<Pair> q = new ArrayDeque<>();
        q.add(new Pair(x, y));

        // get target color
        char target = M[x][y];

        // run till queue is not empty
        while (!q.isEmpty())
        {
            // pop front node from queue and process it
            Pair node = q.poll();

            // (x, y) represents current pixel
            x = node.x;
            y = node.y;

            // replace current pixel color with that of replacement
            M[x][y] = replacement;

            // process all 8 adjacent pixels of current pixel and
            // enqueue each valid pixel
            for (int k = 0; k < row.length; k++)
            {
                // if adjacent pixel at position (x + row[k], y + col[k]) is
                // a valid pixel and have same color as that of current pixel
                if (isSafe(M, m, n, x + row[k], y + col[k], target))
                {
                    // enqueue adjacent pixel
                    q.add(new Pair(x + row[k], y + col[k]));
                }
            }
        }
    }

    public static void main(String[] args)
    {
        // matrix showing portion of the screen having different colors
        char[][] M = {
            "YYYGGGGGGG".toCharArray(),
            "YYYYYYGXXX".toCharArray(),
            "GGGGGGGXXX".toCharArray(),
            "WWWWWGGGGX".toCharArray(),
            "WRRRRRGXXX".toCharArray(),
            "WWWRRGGXXX".toCharArray(),
            "WBWRRRRRRX".toCharArray(),
            "WBBBBRRXXX".toCharArray(),
            "WBBXBBBBXX".toCharArray(),
            "WBBXXXXXXX".toCharArray()
        };

        // start node
        int x = 3, y = 9;   // target color = "X"

        // replacement color
        char replacement = 'C';

        // replace target color with replacement color
        floodfill(M, x, y, replacement);

        // print the colors after replacement
        for (int i = 0; i < M.length; i++) {
            System.out.println(Arrays.toString(M[i]));
        }
    }
}

Finding all classes implementing a specific interface

public <T> List<Class<? extends T>> findAllMatchingTypes(Class<T> toFind) {
    foundClasses = new ArrayList<Class<?>>();
    List<Class<? extends T>> returnedClasses = new ArrayList<Class<? extends T>>();
    this.toFind = toFind;
    walkClassPath();
    for (Class<?> clazz : foundClasses) {
        returnedClasses.add((Class<? extends T>) clazz);
    }
    return returnedClasses;
}

#java #gfg #geeksforgeeks #lecture #sorting #bubblesort

// Optimised Bubble Sort

import java.io.*;

class GFG {
    
    static void bubbleSort(int arr[], int n){
        boolean swapped;
        
        for(int i = 0; i < n; i++){
            
            swapped = false;
            
            for(int j = 0; j < n - i - 1; j++){
                if( arr[j] > arr[j + 1]){
                    
                    // swapping
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    
                    swapped = true;
                    
                }
            }
            if(swapped == false)
            break;
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    bubbleSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");     // OUTPUT : 1 2 3 4
	    }
	}
}






// Bubble Sort

import java.io.*;

class GFG {
    
    static void bubbleSort(int arr[], int n){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n - i - 1; j++){
                if( arr[j] > arr[j + 1]){
                    
                    // swapping
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    
                }
            }
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    bubbleSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");     // OUTPUT : 1 2 3 4
	    }
	}
}

#java #gfg #geeksforgeeks #lecture #sorting #selectionsort

import java.io.*;

class GFG {
    
    static void selectionSort(int arr[], int n){
        for(int i = 0; i < n; i++){
            int min_ind = i;
            
            for(int j = i + 1; j < n; j++){
                if(arr[j] < arr[min_ind]){
                    min_ind = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[min_ind];
            arr[min_ind] = temp;
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    selectionSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");    // OUTPUT : 1 2 3 4
	    }
	}
}

Intent to Start New Activity in Android Studio

// IntendedActivity - the file you wish to open
// CurrentActivity - the file where this code is placed  

Intent intent = new Intent (this, IntendedActivity.class);
    CurrentActivity.this.startActivity(intent);

Insertion Sort in Java

 public void sort(int array[]) { 
     for (int i = 1; i < array.length; i++) { 
          int key = array[i]; 
          int j = i - 1; 
          while (j >= 0 && array[j] > key) { 
              array[j + 1] = array[j]; 
              j = j - 1; 
          } 
          array[j + 1] = key; 
      } 
 }

> More steps

Storing data in SQLite Database in android

public class LocalDatabase extends SQLiteOpenHelper {
         
    private static final String mDatabaseName = "LocalDatabase";
    private static final int mDatabaseVersion = 1;

public LocalDatabase(Context context) {
        super(context, mDatabaseName, null, mDatabaseVersion);
        SQLiteDatabase db = this.getWritableDatabase();
    }      

}

> More steps

Browse more snippets >>