Reverse words in a String
TC O(n) where n is number of words in the String
import java.util.StringJoiner;
class Solution {
public String reverseWords(String s) {
String[] ch = s.split(" ");
int i =0,j=ch.length/2;
while(i<j){
String temp = ch[i];
ch[i] = ch[ch.length-i-1];
ch[ch.length-i-1] = temp;
i++;
}
StringJoiner sJoiner = new StringJoiner(" ");
for(int k =0;k<ch.length;k++){
if(!ch[k].equals(""))
sJoiner.add(ch[k]);
}
return sJoiner.toString().trim();
}
}
Roman to Integer
TC: O(n), where n is size of the String.
class Solution {
public int romanToInt(String s) {
HashMap<Character,Integer> map =new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
int integerValue = 0;
int i = s.length()-1;
while(i>0){
if(s.charAt(i)=='V' && s.charAt(i-1)=='I'){
integerValue+=4;
i=i-2;
}
else if(s.charAt(i)=='X' && s.charAt(i-1)=='I'){
integerValue+=9;
i = i-2;
}
else if(s.charAt(i)=='L' && s.charAt(i-1)=='X'){
integerValue+=40;
i = i-2;
}
else if(s.charAt(i)=='C' && s.charAt(i-1)=='X'){
integerValue+=90;
i = i-2;
}
else if(s.charAt(i)=='D' && s.charAt(i-1)=='C'){
integerValue+=400;
i = i-2;
}
else if(s.charAt(i)=='M' && s.charAt(i-1)=='C'){
integerValue+=900;
i = i-2;
}
else{
integerValue+=map.get(s.charAt(i));
i--;
}
}
if(i==0) integerValue+=map.get(s.charAt(i));
return integerValue;
}
}
Sentences that contains all the given phrases
Note: I was asked this question in MSCI coding interview question
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static void main (String[] args) {
List<String> sentence= new ArrayList<>();
List<String> queries = new ArrayList<>();
sentence.add("bob and alice like to text each other");
sentence.add("bob does not like to ski but does not like to fall");
sentence.add("Alice likes to ski");
queries.add("bob alice");
queries.add("alice");
queries.add("like");
queries.add("non occurance");
System.out.println(get(sentence,queries));
}
public static List<List<Integer>> get(List<String> sentence, List<String> q){
List<List<Integer>> list = new ArrayList<>();
for(int j =0;j<q.size();j++){
List<Integer> res = new ArrayList<>();
String str[] = q.get(j).split(" ");
for(int i =0;i<sentence.size();i++){
String sen = sentence.get(i);
boolean present = true;
for(String s : str){
if(!sen.contains(s)){
present = false;
break;
}
}
if(present){
res.add(i);// sentence index that had s got added
}
}
if(res.isEmpty()){
List<Integer> temp = new ArrayList<>();
temp.add(-1);
list.add(temp);
}
else list.add(res);
}
return list;
}
}
Longest palindromic substring
TC:O(n^2) for using two loops, space c: O(1)
class Solution {
public String longestPalindrome(String s) {
//the lcs approach won't work here
//we will have to use traditional approach of two loops for finding longest
//palindromic subsequence
int start=0;
int length = 1;
int n = s.length();
if(n<2) return s;
for(int i =0;i<n;i++){
int low = i-1;
int high = i+1;
//below will check till how long the index values of high are equal to current index
//which will be palindrome obviously
while(high < n && s.charAt(high) == s.charAt(i)){
high++;
}
//same logic as above for low index
while(low>=0 && s.charAt(low) == s.charAt(i)){
low--;
}
//finally low and high together
while(low >=0 && high<n && s.charAt(low)== s.charAt(high)){
low--;
high++;
}
int len = high-low -1;
if(len> length){
length = len;
start = low+1;
}
}
//if we were to return length of the logest palindromic substring we could have returned 'length';
return s.substring(start,start+length);
}
}
Compare verisons
TC: O(n) ,where n is the length of the longest version string
class Solution {
public int compareVersion(String version1, String version2) {
version1 = version1+".0";
version2 = version2+".0";
String[] a = version1.split("\\.");
String[] b = version2.split("\\.");
int exL = Math.abs(a.length - b.length);
if(a.length > b.length){
char c = '0';
while(exL-->0){
version2 = version2+"."+c;
}
}
else {
char c = '0';
while(exL-->0){
version1 = version1+"."+c;
}
}
/// now two strings are equal
a= version1.split("\\.");
b = version2.split("\\.");
System.out.println(a.length + " "+ b.length);
for(int i =0;i<a.length;i++){
int p = Integer.parseInt(a[i]);
int q = Integer.parseInt(b[i]);
if(p > q) return 1;
if(p < q) return -1;
}
return 0;
}
}
Palindrome partitioning
TC: exponential : O(2^n)
class Solution {
List<List<String>> getPartitions(String s) {
// add logic here
List<List<String>> list = new ArrayList<>();
f(s,0,new ArrayList<>(),list);
return list;
}
public void f(String s, int index, List<String> l,List<List<String>> list){
if(index>=s.length()){
list.add(new ArrayList<>(l));
return;
}
for(int i = index;i<s.length();i++){
if(!isP(s,index,i)) continue;
l.add(s.substring(index,i+1));
f(s,i+1,l,list);
l.remove(l.size()-1);
}
}
public boolean isP(String s, int i,int e){
while(i<=e){
if(s.charAt(i++)!=s.charAt(e--)) return false;
}
return true;
}
}
Latest comments (0)