MY

Posts

[Interview]: URLify

[Interview] URLify: -------------------------------------------------------------------------------------------------------------------------- Question: URLify: Write a method to replace all spaces in a string with ‘%20’, you may assume that the string has sufficient space at the end to hold the additional characters. Example input: ' mr john smith ' output: ' mr %20john%20smith' -------------------------------------------------------------------------------------------------------------------------- Idea 1: Start from the back and start replacing until the character is not ' ', and replace the characters in reverse order. Solution 1： public class Solution{ public String replace(char[] str) { boolean flag = false; StringBuffer sb = new StringBuffer(); for (int i = str.length - 1; i >= 0; i--) { if (str[i] != ' ') flag = true; if (flag == true) { if (str[i] == ' ') { s

[Interview] Check Permutation

[Interview] Check Permutation -------------------------------------------------------------------------------------------------------------------------- Question: Given 2 Strings, write a method to decide if one is a permutation of the other. -------------------------------------------------------------------------------------------------------------------------- Idea 1: count the number of each character in first string and check if the number of each character in the 2nd string is the same as the 1st string. Solution 1： public class Solution{ boolean checker(String str1, String str2) { if (str1.length() != str2.length()) return false; int[] helper = new int[256]; for(int i = 0 ; i<str1.length();i++) { int index = str1.charAt(i); helper[index]++; } for(int i = 0 ; i<str2.length();i++) { int index = str2.charAt(i); helper[index]--; if(helper[index]<0) return false; } return true; } } ---------------------

[Interview] Reverse C-Style String

[Interview] Reverse C/C++ Style String Question: Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.) Solution： public class Solution{ public String reverse(String str) { int p1 = 0; int p2 = str.length() - 1; char temp; char[] c = new char[p2]; c = str.toCharArray(); while (p1 < p2) { temp = c[p1]; c[p1] = c[p2]; c[p2] = temp; p1++; p2--; } return new String(c); } } Complexity Analysis: Time Complexity: \(O(n)\) Space Complexity: \(O(n)\)

[Interview] Check if String has Unique Characters

[Interview] Check if String has Unique Characters Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structure? package com.Array_Strings; /** * @Question: 1-1. Implement an algorithm to determine if a string has all * unique characters What if you can not use additional data * structure? */ public class Ans1_1 { public boolean helper(String str) { boolean[] map = new boolean[256]; for (int i = 0; i < str.length(); i++) { int val = str.charAt(i); if (map[val]) return false; map[val] = true; } return true; } } Complexity Analysis: Time Complexity: \(O(n)\) Space Complexity: \(O(n)\) Here is my Video Explanation

[LeetCode Solution 131]: Palindrome Partitioning

[LeetCode Solution 131]: Palindrome Partitioning ********************************************************************************* Question: Given a string s , partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s . For example, given s = "aab" , Return [ ["aa","b"], ["a","a","b"] ] -------------------------------------------------------------------------------------------------- Recursive Method Strategy We are going to use backtracking to solve this problem, the idea is if we find a palindrome substring, we add it in a temp and go further searching, the idea is as shows in the following picture: Java public class Solution { public List<List<String>> partition(String s) { if (s.length() == 0 || s == null) return null; List<List<String>> res = new ArrayList&

[LeetCode Solution 40]: Combination Sum II

[LeetCode Solution 40]: Combination Sum II ********************************************************************************* Question: Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in C where the candidate numbers sums to T . Each number in C may only be used once in the combination. Note: All numbers (including the target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target, 8 A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] -------------------------------------------------------------------------------------------------- Approach Recursive Method Strategy The idea is same with the [LeetCode Solution 39] Combination Sum , using backtracking method, but the only difference is how to get the value that we have to skip that can help us to avoid the duplication. H

MY

Search This Blog