Microsoft Interview Question
SDE1sCountry: India
O(n^2) algorithm.
Assumed that each word can be used no more than once (by the definition of the permutation).
bool strPermuteFrom(unordered_set<string> &dict, string &str, int pos)
{
if(pos >= str.size())
return true;
if(dict.size() == 0)
return false;
for(int j = pos; j < str.size(); j++){
string w = str.substr(pos, j - pos + 1);
if(dict.find(w) != dict.end()){
dict.erase(w);
int status = strPermuteFrom(dict, str, j+1);
dict.insert(w);
if(status){
if(pos > 0) str.insert(pos, " ");
return status;
}
}
}
return false;
}
bool strPermute(unordered_set<string> &dict, string &str)
{
return strPermuteFrom(dict, str, 0);
}
result:
dictionary = { acting, good, bad, actor, }
badactorgoodact : notconstructible
badactorgoodacting : constructible (bad actor good acting)
badactorbadacting : notconstructible
static void swap(final String[] strings, final int pos1, final int pos2) {
String temp = strings[pos1];
strings[pos1] = strings[pos2];
strings[pos2] = temp;
}
static void permString(String[] strings, int k, int n) {
if (k == n) {
StringBuffer buffer = new StringBuffer();
for (String string : strings) {
buffer.append(string);
}
set.add(buffer.toString());
System.out.println(buffer.toString());
} else {
for (int i = k; i < n; i++) {
swap(strings, i, k);
permString(strings, k + 1, n);
swap(strings, i, k);
}
}
}
public static Boolean isPermutate(String [] strings,String str){
permString(strings, 0, strings.length);
return set.contains(str);
}
public static void main(String[] args){
String[] arr = {"bad", "actor", "good", "acting"};
System.out.println(isPermutate(arr, "badactorgoodacting"));
}
I'm assuming if a character from a word is used than the entire words should be used.
Then:
1. Create an array of n hashtables that carry their initial value as well where n = length of dict;
2. Push each character from each word onto their hash table
3. Check if the long string can be created without any hash table bucket being negative.
4. Check that if current value < initial value, that each bucket is empty.
O(n) where n = sum of all of the characters in the words of dict[]
d1 = {"bad", "actor", "good", "act"};
d2 = {"bad", "actor", "good", "acting"};
def isPerm(s, wordlist):
i = len(s)
for j in xrange(i, -1, -1):
if s[j:i+1] in wordlist:
i = j - 1
return True if i < 0 else False
print isPerm("badactorgoodacting", d1);
print isPerm("actingactor", d2);
print isPerm("badgoodactingactor", d2);
print isPerm("actactor", d2);
print isPerm("actactor", d1);
O(N^2): the for loop runs for N times, and the str[j:i+1] inside every run is O(N)
d1 = {"bad", "actor", "good", "act"};
d2 = {"bad", "actor", "good", "acting"};
def isPerm(s, wordlist):
i = len(s)
for j in xrange(i, -1, -1):
if s[j:i+1] in wordlist:
i = j - 1
return True if i < 0 else False
print isPerm("badactorgoodacting", d1);
print isPerm("actingactor", d2);
print isPerm("badgoodactingactor", d2);
print isPerm("actactor", d2);
print isPerm("actactor", d1);
# O(N^2) because of the str[i:j+1] construction every time
package StringArray;
/**
* Created by brajesh.k on 21/09/16.
*/
public class DictPermutation {
public static boolean isPermutation(String left, String[] dict) {
if (left == null || left.length() == 0) {
return true;
}
for (String word : dict) {
if (left.startsWith(word)) {
return isPermutation(left.substring(word.length()), dict);
}
}
return false;
}
public static void main(String[] args) {
String[] dict = {"actor", "bad", "acting", "good"};
System.out.println(isPermutation("badactorgoodacting", dict));
}
}
/**
* Created by brajesh.k on 21/09/16.
*/
public class DictPermutation {
public static boolean isPermutation(String left, String[] dict) {
if (left == null || left.length() == 0) {
return true;
}
for (String word : dict) {
if (left.startsWith(word)) {
return isPermutation(left.substring(word.length()), dict);
}
}
return false;
}
public static void main(String[] args) {
String[] dict = {"actor", "bad", "acting", "good"};
System.out.println(isPermutation("badactorgoodacting", dict));
}
}
package StringArray;
/**
* Created by brajesh.k on 21/09/16.
*/
public class DictPermutation {
public static boolean isPermutation(String left, String[] dict) {
if (left == null || left.length() == 0) {
return true;
}
for (String word : dict) {
if (left.startsWith(word)) {
return isPermutation(left.substring(word.length()), dict);
}
}
return false;
}
public static void main(String[] args) {
String[] dict = {"actor", "bad", "acting", "good"};
System.out.println(isPermutation("badactorgoodacting", dict));
}
}
package StringArray;
/**
* Created by brajesh.k on 21/09/16.
*/
public class DictPermutation {
public static boolean isPermutation(String left, String[] dict) {
if (left == null || left.length() == 0) {
return true;
}
for (String word : dict) {
if (left.startsWith(word)) {
return isPermutation(left.substring(word.length()), dict);
}
}
return false;
}
public static void main(String[] args) {
String[] dict = {"actor", "bad", "acting", "good"};
System.out.println(isPermutation("badactorgoodacting", dict));
}
}
class CheckPermutation
{
static string[] array = {"actor", "bad", "acting", "good","man"};
private static string value = "actorbadactinggood";
public static void Main()
{
Console.WriteLine("Executing..");
bool x = IsPermutationOfTheString(value, array, 0);
Console.WriteLine(x);
Console.ReadLine();
}
public static bool IsPermutationOfTheString(string text, string[] arr, int i)
{
if (text.Length == 0)
{
return true;
}
if (i == arr.Length && text.Length != 0)
{
return false;
}
string newText = "";
if (text.Contains(arr[i]))
{
int k = text.IndexOf(arr[i], StringComparison.CurrentCulture);
newText = text.Remove(k, arr[i].Length);
return IsPermutationOfTheString(newText, arr, i + 1);
}
return IsPermutationOfTheString(text, arr, i + 1);
}
}
Python code with depth first traversal
def check(string_ans, list_of_word, check_word = ""):
if check_word == string_ans:
return True
for key, val in enumerate(list_of_word):
# print check_word + val
b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
if b == True:
return True
return False
Depth first search solution with python
def check(string_ans, list_of_word, check_word = ""):
if check_word == string_ans:
return True
for key, val in enumerate(list_of_word):
# print check_word + val
b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
if b == True:
return True
return False
Depth first search solution with python
def check(string_ans, list_of_word, check_word = ""):
if check_word == string_ans:
return True
for key, val in enumerate(list_of_word):
# print check_word + val
b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
if b == True:
return True
return False
The best possible solution would be one that traverses the big string only once. This requires list of words to be indexed in a structure that can be transversed linearly, in parallel with the big string, in one pass, achieving a final complexity of O(n).
Trie data structure can be used to solve the problem.
1. First build the trie using the list of words.
2. Now go through the bigger string one by one word and see if it matches with the trie nodes
3.If any point no match is found, return false.
4. If we reach the end of string return true.
private static void permutation(String word, ArrayList<String> prefix, ArrayList<String> dict)
{
int n = dict.size();
if(n == 0 && prefix.size() > 0)
{
String word_ = "";
for(int i = 0; i < prefix.size(); i++)
{
word_ = word_.concat(prefix.get(i));
}
if(word.equals(word_))
System.out.println("true");
}
else
{
ArrayList<String> prefix_;
ArrayList<String> str = Code.clone(dict);
ArrayList<String> str_;
for(int i = 0; i < n; i++)
{
str_ = new ArrayList<String>();
str_.addAll(str.subList(0,i));
str_.addAll(str.subList(i+1,n));
prefix_ = Code.clone(prefix);
prefix_.add(dict.get(i));
permutation(word, prefix_, str_);
}
}
}
private static ArrayList<String> clone(ArrayList<String> words)
{
ArrayList<String> clone = new ArrayList<String>();
for(int i=0; i< words.size(); i++)
{
clone.add(words.get(i));
}
return clone;
}
public static void isPermuted(String word, ArrayList<String> dict)
{
permutation(word, new ArrayList<String>(), dict);
}
private static void permutation(String word, ArrayList<String> prefix, ArrayList<String> dict)
{
int n = dict.size();
if(n == 0 && prefix.size() > 0)
{
String word_ = "";
for(int i = 0; i < prefix.size(); i++)
{
word_ = word_.concat(prefix.get(i));
}
if(word.equals(word_))
System.out.println("true");
}
else
{
ArrayList<String> prefix_;
ArrayList<String> str = Code.clone(dict);
ArrayList<String> str_;
for(int i = 0; i < n; i++)
{
str_ = new ArrayList<String>();
str_.addAll(str.subList(0,i));
str_.addAll(str.subList(i+1,n));
prefix_ = Code.clone(prefix);
prefix_.add(dict.get(i));
permutation(word, prefix_, str_);
}
}
}
private static ArrayList<String> clone(ArrayList<String> words)
{
ArrayList<String> clone = new ArrayList<String>();
for(int i=0; i< words.size(); i++)
{
clone.add(words.get(i));
}
return clone;
}
public static void isPermuted(String word, ArrayList<String> dict)
{
permutation(word, new ArrayList<String>(), dict);
}
public static void main(String[] args) {
String[] d1 = {"bad", "actor", "good", "act"};
String[] d2 = {"bad", "actor", "good", "acting"};
System.out.println(isPermutation("badactorgoodacting", d1));
System.out.println(isPermutation("badactorgoodacting", d2));
String[] d1b = {"bad", "good", "actor", "acting", "action"};
String[] d2b = {"best", "better", "actor", "acting", "movie"};
System.out.println(isPermutation("badgoodaction", d1b));
System.out.println(isPermutation("badgoodactionr", d1b));
System.out.println(isPermutation("betteractingactormovie", d2b));
}
public static boolean isPermutation(String s, String[] w) {
Map<Character, List<String>> mapStrings = new HashMap<>();
for (int i = 0; i < w.length; i++) {
Character key = Character.valueOf(w[i].charAt(0));
if (mapStrings.get(key) != null) {
mapStrings.get(key).add(w[i]);
} else {
List<String> list = new ArrayList<>();
list.add(w[i]);
mapStrings.put(key, list);
}
}
return isPermutation(s, 0, new StringBuilder(), mapStrings, new HashSet<>());
}
public static boolean isPermutation(String s, int start, StringBuilder t, Map<Character, List<String>> w, HashSet<String> usedStrings) {
for (int i = start; i < s.length(); i++) {
if(w.containsKey(s.charAt(i))) {
List<String> l = w.get(s.charAt(i));
Iterator<String> iter = l.iterator();
while (iter.hasNext()) {
String str = iter.next();
// if string fits in remaining length
if (!usedStrings.contains(str) && str.length() <= s.length() - i && s.substring(i, i + str.length()).equals(str)) {
t.append(str);
usedStrings.add(str);
if (t.length() == s.length()) {
return true;
} else if (t.length() < s.length()) {
if(isPermutation(s, i + str.length(), t, w, usedStrings)) {
return true;
}
}
// if no match found using this string prefix remove it
int lastIndex = s.lastIndexOf(str.charAt(0));
if (lastIndex != -1 && lastIndex + str.length() <= t.length() &&
t.substring(lastIndex, lastIndex + str.length()).equals(str)) {
t.delete(lastIndex, lastIndex + str.length());
}
usedStrings.remove(str);
}
}
}
}
return false;
}
}
/*
output:
false
true
true
false
true
*/
"Simplicity is always the key, but making things simple needs practice."
Just use a boolean array to keep track of what is used.
- samudra.agni December 01, 2016