Uber Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))
bool checkOrder(string in, string order) {
unordered_map<char, int> pos;
for(int i = 0; i < in.size(); i++){
pos[in[i]] = i;
}
for(int i = 1; i < order.size(); i++){
if(pos[order[i]] - pos[order[i-1]] < 0){
return false;
}
}
return true;
}
I'm going to make the assumption that there won't be any duplicate characters in the ordering. i.e, in your first example, pattern "hlol!" wouldn't make since sine the first 'l' in the pattern accounts for ALL instances of 'l' in the input.
Swift 2.2
func lastInstanceOf(phrase: String, letter: Character) -> Int? {
for i in (0 ..< phrase.characters.count).reverse() {
if (phrase[phrase.startIndex.advancedBy(i)] == letter) {
return i
}
}
return nil
}
func matchPattern(phrase: String, pattern: String) -> Bool {
for i in 0 ..< pattern.characters.count {
if (i < pattern.characters.count - 1) {
let currentIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(i)])
for j in i + 1 ..< pattern.characters.count {
let compareIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(j)])
if (compareIndex < currentIndex) {
return false
}
}
}
}
return true
}
matchPattern("hello world!", pattern: "hlo!") // false
matchPattern("hello world!", pattern: "!od") // false
matchPattern("hello world!", pattern: "he!") // true
matchPattern("aaaabbbcccc", pattern: "ac") // true
public class Main {
public static void main(String[] args) {
String s = "hello world!" ;
//String orderingPattern = "hlo!";
String orderingPattern = "he!";
if(checkOrderpattern(s,orderingPattern)){
System.out.println("The string is ordered.");
}else{
System.out.println("The string is not ordered.");
}
}
public static boolean checkOrderpattern(String s, String orderingPattern){
for(int i=0;i<orderingPattern.length()-1; i++){
if(!( s.lastIndexOf(orderingPattern.charAt(i)) < s.indexOf(orderingPattern.charAt(i+1)) )){
return false;
}
}
return true;
}
}
def func2(inputstring,orderingstring):
controlmatrix=[[0 for x in range(len(inputstring))] for y in range(len(orderingstring))]
#j=0
for i in range(len(inputstring)):
for j in range(len(orderingstring)):
if inputstring[i]==orderingstring[j]:
controlmatrix[j][i]=i
for k in range(len(orderingstring)-1):
if (max(controlmatrix[k][:])>max(controlmatrix[k+1][:])) or (min(controlmatrix[k][:])<min(controlmatrix[k+1][:])) :
return False
return True
not using indexof function which indirectly iterates over the array for the no. of time it is being used... so guess time complexity will be less for below code
package string;
public class FindSeqString {
public static void main(String[] args) {
FindSeqString fss = new FindSeqString();
System.out.println(fss.checkStringSeq("hellow", "helow")?"Seq match found":"Seq not found");
System.out.println(fss.checkStringSeq("yellow","ylow")?"Seq match found":"Seq not found");
System.out.println(fss.checkStringSeq("hhhhellllow","hlleow")?"Seq match found":"Seq not found");
}
public boolean checkStringSeq(String parentString,String findSeq){
char[] parentCharArray = parentString.toCharArray();
char[] seqCheckCharArray= findSeq.toCharArray();
int seqCheckIndex=0;
if(parentCharArray.length<seqCheckCharArray.length)
return false;
for (char c : parentCharArray){
if(seqCheckIndex!= seqCheckCharArray.length){
if(c==seqCheckCharArray[seqCheckIndex])
seqCheckIndex++;
}
}
if (seqCheckIndex!= seqCheckCharArray.length)
return false;
else
return true;
}
}
public final class StringOrderingChecker {
private static boolean isStringOrdered(final String input, final String ordered) {
final Map<Character, Integer> lastIndexByCharacter = new HashMap<>(input.length());
int position = 0;
for (final char character : input.toCharArray()) {
lastIndexByCharacter.put(character, position++);
}
int previousPosition = 0;
for (final char character : ordered.toCharArray()) {
final Integer characterLastIndex = lastIndexByCharacter.get(character);
if (characterLastIndex == null) {
continue;
}
if (previousPosition > characterLastIndex) {
return false;
}
previousPosition = characterLastIndex;
}
return true;
}
public static void main(String[] args) {
System.out.println(isStringOrdered("hello world!", "hlo"));
}
}
and
public final class StringOrderingChecker {
private static boolean isStringOrdered(final String input, final String ordered) {
final Map<Character, Integer> lastIndexByCharacter = new HashMap<>(input.length());
int position = 0;
for (final char character : input.toCharArray()) {
lastIndexByCharacter.put(character, position++);
}
int previousPosition = 0;
for (final char character : ordered.toCharArray()) {
final Integer characterLastIndex = lastIndexByCharacter.get(character);
if (characterLastIndex == null) {
continue;
}
if (previousPosition > characterLastIndex) {
return false;
}
previousPosition = characterLastIndex;
}
return true;
}
public static void main(String[] args) {
System.out.println(isStringOrdered("hello world!", "hlo"));
}
}
and
public static void checkorder(char[] bword, char [] sword)
{
int start = 0;
int success = 0;
for (int i = 0; i < sword.Length; i++)
{
for (int x = bword.Length-1; x >= start; x--)
{
if (sword[i] == bword[x])
{
start = x;
success++;
break;
}
}
}
if (success == sword.Length)
{
Console.WriteLine("True");
}
else
Console.WriteLine("False");
}
Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))
bool checkOrder(string in, string order) {
unordered_map<char, int> pos;
for(int i = 0; i < in.size(); i++){
pos[in[i]] = i;
}
for(int i = 1; i < order.size(); i++){
if(pos[order[i]] - pos[order[i-1]] < 0){
return false;
}
}
return true;
}
public static void main(String[] args) {
// TODO code application logic here
Scanner in=new Scanner(System.in);
String s1=in.next();
String s2=in.next();
// char str1[]=s1.toCharArray();
char str2[]=s2.toCharArray();
StringBuffer str=new StringBuffer();
for(int i=0;i<=s2.length()-1;i++)
{
//for(int j=i;j<s1.length();j++)
{
int n=s1.lastIndexOf(str2[i]);
str.append(str2[i]);
s1=s1.substring(n+1);
}
}
if(s2.equals(str))
{
System.out.println("true");
}
else
{
System.out.println("false");
}
}
public class RelativeStringOrder {
public static void main(String[] args) {
String input ="aaaabbbcccc";
String order ="ac";
boolean ordered = isStringOrdered(input,order);
System.out.println("The given String is ordered:"+ordered);
}
/*
* o(n) with extra space
*/
private static boolean isStringOrdered(String input, String order) {
HashMap<Character,Integer> orderMap = new HashMap<>();
for(int i = 0 ; i<input.length();i++){
orderMap.put(input.charAt(i), i);
}
for(int i=0;i<order.length()-1;i++){
if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
return false;
}
}
return true;
}
}
public class RelativeStringOrder {
public static void main(String[] args) {
String input ="aaaabbbcccc";
String order ="ac";
boolean ordered = isStringOrdered(input,order);
System.out.println("The given String is ordered:"+ordered);
}
/*
* o(n) with extra space
*/
private static boolean isStringOrdered(String input, String order) {
HashMap<Character,Integer> orderMap = new HashMap<>();
for(int i = 0 ; i<input.length();i++){
orderMap.put(input.charAt(i), i);
}
for(int i=0;i<order.length()-1;i++){
if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
return false;
}
}
return true;
}
}
public class RelativeStringOrder {
public static void main(String[] args) {
String input ="aaaabbbcccc";
String order ="ac";
boolean ordered = isStringOrdered(input,order);
System.out.println("The given String is ordered:"+ordered);
}
/*
* o(n) with extra space
*/
private static boolean isStringOrdered(String input, String order) {
HashMap<Character,Integer> orderMap = new HashMap<>();
for(int i = 0 ; i<input.length();i++){
orderMap.put(input.charAt(i), i);
}
for(int i=0;i<order.length()-1;i++){
if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
return false;
}
}
return true;
}
public class RelativeStringOrder {
public static void main(String[] args) {
String input ="aaaabbbcccc";
String order ="ac";
boolean ordered = isStringOrdered(input,order);
System.out.println("The given String is ordered:"+ordered);
}
/*
* o(n) with extra space
*/
private static boolean isStringOrdered(String input, String order) {
HashMap<Character,Integer> orderMap = new HashMap<>();
for(int i = 0 ; i<input.length();i++){
orderMap.put(input.charAt(i), i);
}
for(int i=0;i<order.length()-1;i++){
if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
return false;
}
}
return true;
}
}
def func (input, ordering):
pos = {}
for i, char in enumerate(input):
pos[char] = pos.get(char, []) + [i]
n = len(ordering)
for j in range(n-1):
first = ordering[j]
second = ordering[j+1]
for order1 in pos[first]:
for order2 in pos[second]:
if order1 < order2:
continue
else:
return False
return True
Linear approach runs in O(m+n)
Implementation in golang:
func checkOrder(input string, order string) bool{
// Maps a char to an array. First element is the first appearance of
// the char and the second element is the last appearance of the char
var m = make(map[string][]int)
// Runs through the input once to determine the first and last
// instance of each char
for i := 0; i < len(input); i++{
if m[ string(input[i]) ] == nil{
m[ string(input[i]) ] = []int{ i , i };
}else{
m[ string(input[i]) ] = []int{ m[ string(input[i]) ][0] , i };
}
}
// Runs through the order and use the map to see if order
// is enforced
for i := 1; i < len(order); i++{
if m[string(order[i])][0] < m[string(order[i - 1])][1]{
return false;
}
}
return true
}
Implementation in Java:
public static boolean checkOrder(String input, String order){
HashMap<String, int[]> map = new HashMap<String, int[]>();
for(int i = 0; i < input.length(); i++){
if ( !map.containsKey(input.substring(i,i+1)) ){
int[] arr = {i, i};
map.put(input.substring(i,i+1), arr);
}else{
int[] arr = {map.get(input.substring(i,i+1))[0] , i};
map.put(input.substring(i,i+1), arr);
}
}
for(int i = 1; i < order.length(); i++){
if(map.get(order.substring(i, i+1))[0] < map.get(order.substring(i - 1, i))[1] ){
return false;
}
}
return true;
}
#include <iostream>
#include <string>
using namespace std;
bool checkOrdering(string a, string b) {
int order[b.length()];
for (int i=0;i<b.length();i++){
int pos = a.rfind(b[i]);
order[i]=pos;
}
for (int i=0;i<(sizeof(order)/sizeof(order[0]))-1;i++){
if (order[i]==string::npos || order[i]>order[i+1]){
return false;
}
}
return true;
}
C++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
char str[100];
char pattern[100];
unordered_map<char, int> positions;
int farthest_pos;
cout<<"Enter main string: ";
cin >> str;
cout<<"string is : "<<str<<endl;
cout<<"pattern : ";
cin>>pattern;
cout<<"pattern is : "<<pattern<<endl;
for (int i=0; i < strlen(str); i++) {
positions[str[i]] = i;
}
farthest_pos = positions[pattern[0]];
for (int j=0; j < strlen(pattern)-1; j++)
{
if (positions[pattern[j]] > positions[pattern[j+1]]) {
cout<<"Problemm is: "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
cout <<"false"<<endl;
return 0;
}
}
cout <<"true"<<endl;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
char str[100];
char pattern[100];
unordered_map<char, int> positions;
int farthest_pos;
cout<<"Enter main string: ";
cin >> str;
cout<<"string is : "<<str<<endl;
cout<<"pattern : ";
cin>>pattern;
cout<<"pattern is : "<<pattern<<endl;
for (int i=0; i < strlen(str); i++) {
positions[str[i]] = i;
}
farthest_pos = positions[pattern[0]];
for (int j=0; j < strlen(pattern)-1; j++)
{
if (positions[pattern[j]] > positions[pattern[j+1]]) {
cout<<"Problemm is: "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
cout <<"false"<<endl;
return 0;
}
}
cout <<"true"<<endl;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
char str[100];
char pattern[100];
unordered_map<char, int> positions;
int farthest_pos;
cout<<"Enter main string: ";
cin >> str;
cout<<"string is : "<<str<<endl;
cout<<"pattern : ";
cin>>pattern;
cout<<"pattern is : "<<pattern<<endl;
for (int i=0; i < strlen(str); i++) {
positions[str[i]] = i;
}
farthest_pos = positions[pattern[0]];
for (int j=0; j < strlen(pattern)-1; j++)
{
if (positions[pattern[j]] > positions[pattern[j+1]]) {
cout<<"Problemm is: "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
cout <<"false"<<endl;
return 0;
}
}
cout <<"true"<<endl;
}
import java.util.HashMap;
import java.util.Map;
public class OrderingProblem {
public static void main(String[] args) {
OrderingProblem orderingProblem = new OrderingProblem();
System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "hlo!"));
System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "!od"));
System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "he!"));
System.out.println("Result = " + orderingProblem.checkStringOrdering("aaaabbbcccc", "ac"));
}
private boolean checkStringOrdering(String source, String target) {
if (null == source || null == target || 0 == source.length() || 0 == target.length()) {
return true;
}
// Collect the first occurrence of all the chars in target string
Map<Character, Integer> mapOfFirstOccurence = new HashMap<Character, Integer>();
for (int i = 0; i < target.length(); i++) {
if (null != mapOfFirstOccurence.get(target.charAt(i))) {
continue;
}
for (int j = 0; j < source.length(); j++) {
if (source.charAt(j) == target.charAt(i)) {
mapOfFirstOccurence.put(target.charAt(i), j);
break;
}
}
}
for (int i = 0; i < target.length(); i++) {
// find the last occurrence of target.charAt(i) within source string
int lastOccurenceIndex = -1;
for (int j = source.length() - 1; j >= 0; j--) {
if (source.charAt(j) == target.charAt(i)) {
lastOccurenceIndex = j;
break;
}
}
if (lastOccurenceIndex == -1) {
// Did not find any match
return false;
}
// Check all the chars after the current target's character if they are appearing before the last occurence of target's char in source string
for (int k = i + 1; k < target.length(); k++) {
Integer firstOccurrenceIndex = mapOfFirstOccurence.get(target.charAt(k));
if (null == firstOccurrenceIndex) {
continue;
}
if (firstOccurrenceIndex < lastOccurenceIndex) {
return false;
}
}
}
return true;
}
}
/**
* N - str.length()
* M - order.length()
* <p>
* time: O(N+M)
* space: O(M)
*/
public static boolean hasCorrectOrdering(String str, String order) {
checkNotNull(str, "null 'str' parameter passed");
checkNotNull(order, "null 'order' parameter passed");
if (order.length() > str.length()) {
return false;
}
final int orderLength = order.length();
Map<Character, Integer> orderIndex = new HashMap<>();
for (int i = 0; i < orderLength; ++i) {
if (orderIndex.put(order.charAt(i), i) != null) {
throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
}
}
int lastIndex = -1;
for (int i = 0, length = str.length(); i < length; ++i) {
char ch = str.charAt(i);
if (orderIndex.containsKey(ch)) {
int curIndex = orderIndex.get(ch);
// check 1st character is hit properly
if (lastIndex == -1 && curIndex != 0) {
return false;
}
// check other characters
else if (curIndex < lastIndex) {
return false;
}
lastIndex = curIndex;
}
}
// check we found all characters from 'order'
return lastIndex == orderLength - 1;
}
/**
* N - str.length()
* M - order.length()
* <p>
* time: O(N+M)
* space: O(M)
*/
public static boolean hasCorrectOrdering(String str, String order) {
checkNotNull(str, "null 'str' parameter passed");
checkNotNull(order, "null 'order' parameter passed");
if (order.length() > str.length()) {
return false;
}
final int orderLength = order.length();
Map<Character, Integer> orderIndex = new HashMap<>();
for (int i = 0; i < orderLength; ++i) {
if (orderIndex.put(order.charAt(i), i) != null) {
throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
}
}
int lastIndex = -1;
for (int i = 0, length = str.length(); i < length; ++i) {
char ch = str.charAt(i);
if (orderIndex.containsKey(ch)) {
int curIndex = orderIndex.get(ch);
// check 1st character is hit properly
if (lastIndex == -1 && curIndex != 0) {
return false;
}
// check other characters
else if (curIndex < lastIndex) {
return false;
}
lastIndex = curIndex;
}
}
// check we found all characters from 'order'
return lastIndex == orderLength - 1;
}
/*
* N - str.length()
* M - order.length()
* <p>
* time: O(N+M)
* space: O(M)
*/
public static boolean hasCorrectOrdering(String str, String order) {
checkNotNull(str, "null 'str' parameter passed");
checkNotNull(order, "null 'order' parameter passed");
if (order.length() > str.length()) {
return false;
}
final int orderLength = order.length();
Map<Character, Integer> orderIndex = new HashMap<>();
for (int i = 0; i < orderLength; ++i) {
if (orderIndex.put(order.charAt(i), i) != null) {
throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
}
}
int lastIndex = -1;
for (int i = 0, length = str.length(); i < length; ++i) {
char ch = str.charAt(i);
if (orderIndex.containsKey(ch)) {
int curIndex = orderIndex.get(ch);
// check 1st character is hit properly
if (lastIndex == -1 && curIndex != 0) {
return false;
}
// check other characters
else if (curIndex < lastIndex) {
return false;
}
lastIndex = curIndex;
}
}
// check we found all characters from 'order'
return lastIndex == orderLength - 1;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Created by dushyant.sabharwal on 11/20/16.
*/
public class OrderingString {
public static void main(String []args) throws IOException {
System.out.println("Please enter the main string");
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String main = bufferedReader.readLine();
System.out.println("Please enter the ordering string");
String ordering = bufferedReader.readLine();
bufferedReader.close();
int [] order = new int[ordering.length()];
for (int i=0; i < ordering.length(); i++) {
order[i] = main.lastIndexOf(ordering.charAt(i));
}
int i;
if (order.length > 1) {
for (i = 0; i < order.length - 1; i++) {
if (order[i] == -1 || order[i] > order[i + 1]) {
break;
}
}
if (i == order.length - 1) {
System.out.println("TRUE");
} else {
System.out.println("FALSE");
}
} else {
System.out.println(-1 != main.lastIndexOf(ordering.charAt(0)));
}
}
}
class Solution {
public static void main (String[] args) {
String input = "aaaabbbcccc", ordering = "ac";
System.out.println(isPresent(input, ordering));
}
private static boolean isPresent(String input, String ordering) {
int n = input.length(), m = ordering.length();
int[] arr = new int[256];
for (int i = 0; i < n; i++) {
arr[input.charAt(i)] = i;
}
for (int j = 1; j < m; j++) {
if (arr[ordering.charAt(j)] < arr[ordering.charAt(j - 1)]) {
return false;
}
}
return true;
}
}
public class StringOrdering {
public static boolean checkOrdering(String s, String order) {
String ss = "";
char ch;
for (int i=0; i<s.length(); i++) {
ch = s.charAt(i);
if (order.contains(ch + "")) {
if (ss.length()> 0 && ss.charAt(ss.length() -1) == ch) {
} else {
ss+= ch;
}
}
}
System.out.println(ss);
if (ss.equals(order)) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
System.out.println(checkOrdering("hello world!", "hlo!"));
System.out.println(checkOrdering("hello world!", "!od"));
System.out.println(checkOrdering("hello world!", "he!"));
System.out.println(checkOrdering("aaaabbbcccc", "ac"));
}
}
public class StringOrdering {
public static boolean checkOrdering(String s, String order) {
String ss = "";
char ch;
for (int i=0; i<s.length(); i++) {
ch = s.charAt(i);
if (order.contains(ch + "")) {
if (ss.length()> 0 && ss.charAt(ss.length() -1) == ch) {
} else {
ss+= ch;
}
}
}
System.out.println(ss);
if (ss.equals(order)) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
System.out.println(checkOrdering("hello world!", "hlo!"));
System.out.println(checkOrdering("hello world!", "!od"));
System.out.println(checkOrdering("hello world!", "he!"));
System.out.println(checkOrdering("aaaabbbcccc", "ac"));
}
}
I can see many of the solutions in Java are using String.indexOf() function which is O(n) complexity. My solution with a trade-of of O(n) space complexity does the operation in O(n) time. I use two HashSets , one with already traversed characters which aren't allowed to occur in the string and another with allowed set of characters. I move a character from the second to the first HashSet whenever I encounter an allowed character. I also use a temp character variable to detect the last character added to the first HashSet since this is the only character in the first HashSet which is allowed to present in the string. Please let me know if you find any problem with the solution.
public static boolean findOrdered(String str1, String str2){
if(str1==null||str2==null||str1.length()<=1||str2.length()<=1)
return true;
HashSet<Character> charList = new HashSet<>();
for(int i=0;i<str2.length();i++)
charList.add(str2.charAt(i));
char temp=str2.charAt(0);
HashSet<Character> traversedCharList = new HashSet<>();
int j=0;
for(int i=0;i<str1.length();i++){
if(str1.charAt(i)==str2.charAt(j)) {
traversedCharList.add(str2.charAt(j));
temp=str2.charAt(j);
charList.remove(str2.charAt(j));
j=(j==str2.length()-1)?j:j+1;
} else if(charList.contains(str1.charAt(i))) {
while(str2.charAt(j)!=str1.charAt(i)){
traversedCharList.add(str2.charAt(j));
charList.remove(str2.charAt(j++));
}
traversedCharList.add(str2.charAt(j));
temp=str2.charAt(j);
charList.remove(str2.charAt(j));
} else if(traversedCharList.contains(str1.charAt(i))&&temp!=str1.charAt(i)) {
return false;
}
}
return true;
}
public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}
for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}
public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}
for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}
public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}
for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}
public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}
for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}
#include<iostream>
#include<unordered_map>
#include<string>
using namespace std;
bool stringOrdering(string s1, string s2)
{
unordered_map<char,int> map;
for(int i=0;i<s1.length();i++)
{
map[s1[i]] = i;
}
int idx = -1;
for(int i=0;i<s2.length();i++)
{
if(idx < map[s2[i]])
idx = map[s2[i]];
else
return false;
}
return true;
}
int main()
{
cout << stringOrdering("hello world!","hlo!") << endl;
cout << stringOrdering("hello world!","he!") << endl;
cout << stringOrdering("aaaaaabbcc","ac") << endl;
cout << stringOrdering("hello world!", "!od") << endl;
return 0;
}
/**
* Javascript Implementation.
* validateStringWithPattern
Given an input string and ordering string, need to return true if
the ordering string is present in Input string.
input = "hello world!"
ordering = "hlo!"
result = FALSE (all Ls are not before all Os)
input = "hello world!"
ordering = "!od"
result = FALSE (the input has '!' coming after 'o' and after 'd',
but the pattern needs it to come before 'o' and 'd')
input = "hello world!"
ordering = "he!"
result = TRUE
input = "aaaabbbcccc"
ordering = "ac"
result = TRUE
*/
function validateStringWithPattern(str, pattern) {
let map = {};
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if(map[char]) {
map[char].push(index);
} else {
map[char] = [index];
}
}
for(let index = 1, length = pattern.length; index < length; index++) {
let mapCharArr1 = map[pattern[index-1]];
let mapCharArr2 = map[pattern[index]];
//First index of second char should be more than the last index of first char.
if(mapCharArr2[0] < mapCharArr1[mapCharArr1.length - 1]){
return false;
}
}
return true;
}
//Test Case 1
let str = 'hello world!';
let pattern1 = 'hlo!';
let pattern2 = '!od';
let pattern3 = 'he!';
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1 + "' ===> " + validateStringWithPattern(str, pattern1));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern2 + "' ===> " + validateStringWithPattern(str, pattern2));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern3 + "' ===> " + validateStringWithPattern(str, pattern3));
//Test Case 2
str = 'aaaabbbcccc';
pattern1 = 'ac';
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1 + "' ===> " + validateStringWithPattern(str, pattern1));
def check_order(input, ordering):
chars_in_ordering = set([char for char in ordering])
chars_to_process = iter(ordering)
target_char = chars_to_process.next()
processed = set()
for i in input:
if i == target_char or i not in chars_in_ordering:
pass
elif i in processed:
return False
else:
processed.add(target_char)
target_char = chars_to_process.next()
return True
func checkIfOrdered(_ mainStr : String, _ subStr : String) -> Bool {
var indexesOfChars = [Int]()
for ch in subStr {
var currentIndex = -1
for (i,str) in mainStr.enumerated() {
if (String(str) == String(ch)) {
currentIndex = i
}
}
indexesOfChars.append(currentIndex)
}
if indexesOfChars.contains(-1) {
return false
}
return indexesOfChars == indexesOfChars.sorted()
}}}
- Arun Vadivel August 05, 2016