obed.tandadjaja
BAN USERI think the other answers missed the hardest part of this problem which is to make sure that overlap between two or more substrings will be under the same bold tag.
For example:
String = "HelloWorld HelloWorld"
Substrings = {"el", "llo", "rl"}
Output = "H<b>ello</b>Wo<b>rl</b>d H<b>ello</b>Wo<b>rl</b>d"
Another example:
String = "HelloWorld HelloWorld";
Substrings = {"He", "el", "llo", "oW", "Wor", "rl", "ld"};
Output = "<b>HelloWorld</b> <b>HelloWorld</b>"
import java.util.*;
public class BoldSubstring {
public static void main(String[] args) {
String s = "HelloWorld HelloWorld";
String[] substrings = {"el", "llo", "rl"};
System.out.println(boldenSubstring(s, substrings));
}
public static String boldenSubstring(String s, String[] substrings) {
boolean currentBold = false;
StringBuilder sb = new StringBuilder();
int currentBoldLength = 0;
for(int i = 0; i < s.length(); i++) {
String currentString = s.substring(i);
boolean hasSubstring = false;
for(int j = 0; j < substrings.length; j++) {
if(currentString.indexOf(substrings[j]) == 0) {
if(!currentBold) {
currentBold = true;
sb.append("<b>");
}
currentBoldLength = Math.max(currentBoldLength, substrings[j].length());
}
}
sb.append(s.charAt(i));
if(hasSubstring == false && currentBoldLength == 1) {
if(currentBold) {
currentBold = false;
sb.append("</b>");
}
}
if(currentBoldLength > 0) currentBoldLength--;
}
return sb.toString();
}
}
For this problem I think we should use heap to make sure that upon every insert, we keep the order in place. And to implement this heap functionality, I used Collections.binarysearch to get the index of where I should place the element. From there we can use ArrayList add which allows us to add the element to our desired index.
Insertion complexity: O(n log n)
Query complexity: O(n log n)
Space complexity: O(n)
Median complexity: O(1)
The following is my java code:
import java.util.*;
public class MedianAge {
ArrayList<Integer> ages;
public static void main(String[] args) {
MedianAge ma = new MedianAge();
Scanner sc = new Scanner(System.in);
while(true) {
int num = sc.nextInt();
ma.add(num);
}
}
public MedianAge() {
ages = new ArrayList<>();
}
public void add(int age) {
int index = Collections.binarySearch(ages, age);
if(index < 0) {
index = Math.abs(index)-1;
}
ages.add(index, age);
System.out.println(getMedian());
System.out.println(ages.toString());
}
public double getMedian() {
int mid = ages.size()/2;
if(ages.size() % 2 == 1) return ages.get(mid);
else return (ages.get(mid)+ages.get(mid-1))/2.0;
}
}
The following is my implementation of the SnakeGame
I am just using a int[][] grid and a doubly linkedlist to keep track of the snake body
When the snake eats the food, i add a cell to the head
When the snake moves, i add the new cell to the head and remove its tail
The game is over when snake eats itself, move out of bounds, or when its size == grid.length*grid.length
Because I am not using fancy Java GUI for this, I purposefully did not make the snake to automatically move forward to the direction it is facing. Instead, I have the user to move the snake one cell at a time using prompt.
time complexity: O(n)
space complexity: O(2n)
The following is the code:
import java.util.*;
public class SnakeGame {
int[][] grid;
DoublyLinkedList dll;
public static void main(String[] args) {
SnakeGame sg = new SnakeGame(Integer.parseInt(args[0]));
}
public SnakeGame(int bounds) {
grid = new int[bounds][bounds];
dll = new DoublyLinkedList();
play();
}
public void play() {
startingPoint();
placeFood();
printGrid();
while(true) {
try {
getMove();
printGrid();
} catch(GameOverException e) {
System.out.println(e.getMessage());
return;
}
}
}
public void getMove() throws GameOverException {
Scanner sc = new Scanner(System.in);
String input = sc.next();
int currentRow = dll.head.position[0];
int currentCol = dll.head.position[1];
if(input.equals("w")) {
currentRow--;
} else if(input.equals("a")) {
currentCol--;
} else if(input.equals("s")) {
currentRow++;
} else if(input.equals("d")) {
currentCol++;
} else {
getMove();
return;
}
if(currentCol < 0 || currentCol == grid.length || currentRow < 0 || currentRow == grid.length)
throw new GameOverException("You hit a wall");
else if(grid[currentRow][currentCol] == 1) throw new GameOverException("You ate yourself");
else if(grid[currentRow][currentCol] == 7) {
dll.addFront(currentRow, currentCol);
if(dll.size == grid.length*grid.length) throw new GameOverException("You won!");
placeFood();
} else {
dll.addFront(currentRow, currentCol);
dll.removeTail();
}
}
public int[] getRandomPosition() {
Random r = new Random();
int row, col;
do {
row = r.nextInt(grid.length);
col = r.nextInt(grid.length);
} while(grid[row][col] != 0);
int[] result = {row, col};
return result;
}
public void startingPoint() {
int[] position = getRandomPosition();
dll.addFront(position[0], position[1]);
grid[position[0]][position[1]] = 1;
}
public void placeFood() {
int[] position = getRandomPosition();
grid[position[0]][position[1]] = 7;
}
public void printGrid() {
for(int i = 0; i < grid.length; i++) {
System.out.println(Arrays.toString(grid[i]));
}
}
public class DoublyLinkedList {
Node head, tail;
int size = 0;
public DoublyLinkedList() {
head = null; tail = null;
}
public void addFront(int row, int col) {
if(head == null && tail == null) {
head = tail = new Node(null, row, col, null);
} else if(head == tail) {
head = new Node(null, row, col, tail);
tail.prev = head;
} else {
head = new Node(null, row, col, head);
head.next.prev = head;
}
grid[row][col] = 1;
size++;
}
public void removeTail() {
if(tail == null) {
return;
} else if(head == tail) {
grid[tail.position[0]][tail.position[1]] = 0;
head = tail = null;
} else {
grid[tail.position[0]][tail.position[1]] = 0;
tail = tail.prev;
tail.next = null;
}
size--;
}
}
public class Node {
int[] position;
Node next;
Node prev;
public Node(Node prev, int row, int col, Node next) {
int[] pos = {row, col};
position = pos;
this.next = next;
this.prev = prev;
}
}
public class GameOverException extends Exception {
public GameOverException(String message) {
super(message);
}
}
}
Another approach you can use for space efficiency is to just use grid and implement the snake inside the grid. You can do this by doing the following:
(1) set empty spaces as 0
(2) set food as -1
(3) set snake body as positive integers more than 0
The way this works is that whenever you move the snake, you set the grid to 1 and increment every integer in the grid more than 0 while keeping track of the highest number (the tail). And at the end of this loop, you just make the tail 0. This follows that when the snake eats the food, you just don't delete the highest number.
Time complexity: O(n^2)
Space complexity: O(n)
I believe my code is easier to understand than the other answer, and it handles the problem of when there is a comment inside of a comment
time complexity: O(n)
space complexity: O(1)
import java.util.*;
public class FindCommentsJava {
public static void main(String[] args) {
String s =
"/* //file created by aonecode.com\\n" +
"welcome// to the tech blog */ \\n" +
"// main /*method*/\\n"+
"public static void main(String[] args) {\\n"+
" System.out.println(\"welcome\");//output\\n"+
"}";
try {
ArrayList<String> comments = getComments(s);
System.out.println(comments.toString());
} catch (InvalidSyntaxException e) {
System.out.println(e.getMessage());
}
}
public static ArrayList<String> getComments(String s) throws InvalidSyntaxException {
ArrayList<String> comments = new ArrayList<String>();
boolean currentSingleComment = false;
boolean currentMultiLineComment = false;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length()-1; i++) {
if(s.charAt(i) == '\\' && s.charAt(i+1) == 'n' && currentSingleComment) {
currentSingleComment = false;
comments.add(sb.toString());
sb = new StringBuilder();
i++;
} else if(s.charAt(i) == '*' && s.charAt(i+1) == '/' && currentMultiLineComment) {
currentMultiLineComment = false;
comments.add(sb.toString());
sb = new StringBuilder();
i++;
} else if(currentSingleComment || currentMultiLineComment) {
sb.append(s.charAt(i));
} else if(s.charAt(i) == '/' && s.charAt(i+1) == '/') {
currentSingleComment = true;
i++;
} else if(s.charAt(i) == '/' && s.charAt(i+1) == '*') {
currentMultiLineComment = true;
i++;
}
}
if(sb.length() > 0) throw new InvalidSyntaxException("Comment syntax error");
return comments;
}
public static class InvalidSyntaxException extends Exception {
public InvalidSyntaxException(String message) {
super(message);
}
}
}
The following is the code if you so choose to do the Trie approach
import java.io.*;
import java.util.*;
public class LongestStringDictionary {
public static void main(String[] args) {
Trie t = new Trie();
t.add("apple");
t.add("ale");
t.add("monkey");
t.add("plea");
System.out.println(t.findLongestString("abpcplea"));
}
public static class Trie {
Node root;
public Trie() {
this.root = new Node();
}
public void add(String s) {
Node current = root;
for(int i = 0; i < s.length(); i++) {
add(current, s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
public void add(Node root, char c) {
if(root == null) return;
if(!root.children.containsKey(c)) root.children.put(c, new Node());
}
public String findLongestString(String s) {
String currentLongest = "";
int index = 0;
while(index+currentLongest.length() < s.length()) {
Node current = root;
StringBuilder sb = new StringBuilder();
for(int i = index; i < s.length(); i++) {
if(current.children.containsKey(s.charAt(i))) {
sb.append(s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
if(sb.length() > currentLongest.length()) {
currentLongest = sb.toString();
}
index++;
}
return currentLongest;
}
}
public static class Node {
HashMap<Character, Node> children;
public Node() {
this.children = new HashMap<>();
}
}
}
- obed.tandadjaja February 01, 2017