Microsoft Interview Question SDE-2s
Country: United States
Interview Type: In-Person
srterpe very cleverly inverted the problem. I love the idea. Hats off.
Instead of finding all possible words (sub sequences)
a string can generate, which is my stupid idea,
srterpe is counting the no of characters on each word,
and is a word can be made by taking / loaning characters from the string.
Very very clever.
My code has no chance surviving in more then 24 letter strings - he will win hand down for any string with size more than 20 ish - which is the size of a dictionary ( 2^20 ) .
srterpe is slightly off on the complexity, my algo runs with a complexity of Theta(2^n) where n is the size of the input string, it is close to n! where srterpe is correct.
No matter how large the string becomes, srterpe's method would be on size of the dictionary * no of char in the word.
See more on [ en.wikipedia.org/wiki/Longest_word_in_English ]
Here is to srterpe :
DICT = [ "go","bat","me","eat","goal", "boy", "run" ]
list_of_msets = list ( DICT ) -> { [ mset( $.o.value ) , $.o ] }
LETTERS = [ _'e' , _'o' , _'b', _'a' , _'m', _'g' , _'l' ]
mset_letters = mset( LETTERS )
words = select( list_of_msets ) :: { $.left <= mset_letters } -> { $.right }
println( words )
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
public class Dictionary {
public static void main(String[] args) {
long startTime = new Date().getTime();
char[] arr = {'e','o','b','a','m','g','l'};
List<String> dictionary = new ArrayList<String>(Arrays.asList("go","bat","me","eat","goal","boy","run"));
List<String> match = new ArrayList<String>();
for(int maxWordLength = 2; maxWordLength <= arr.length; maxWordLength++){
possibleStrings(maxWordLength, arr,"",match,dictionary);
}
System.out.println(match);
long endTime = new Date().getTime();
System.out.println(endTime - startTime);
}
public static void possibleStrings(int maxLength, char[] alphabet, String curr,List<String> match, List<String> dictionary) {
// If the current string has reached it's maximum length
if(curr.length() == maxLength) {
// System.out.println(curr);
if(dictionary.contains(curr)){
match.add(curr);
}
// Else add each letter from the alphabet to new strings and process these new strings again
} else {
for(int i = 0; i < alphabet.length; i++) {
String oldCurr = curr;
curr += alphabet[i];
possibleStrings(maxLength,alphabet,curr,match,dictionary);
curr = oldCurr;
}
}
}
}
I created custom class called StringWithCount which will have String word, length and occurance variable.
I am using Hashtable to map charater to the List<StringWithOccurance>.
Then I read the dictionary and create StringWithCount from each string where word and length are explicit, and occurance as 0. For each character in that string, I attach those StringWithCount in that characters list in Hashtable.
This is all my pre-computation. Now when you get the character array, read each character and increment occurance of each StringWithCount for that character in Hashtable. When for any StringWithCount occurance is same as length, add that to answer list.
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class StringWithCount
{
public String word;
public int len;
public int occurance;
public StringWithCount(String w, int l)
{
word=w;
len=l;
occurance=0;
}
}
class Solution
{
public static void main(String[] args)
{
String[] dict = {"meo","got","mov","aaa","cvc","cvf","fbb","wersc"};
Hashtable<Character, ArrayList<StringWithCount>> hst = new Hashtable<>();
for(String word : dict)
{
int len=word.length();
StringWithCount sc = new StringWithCount(word, len);
for(int i=0;i<len;i++)
{
ArrayList<StringWithCount> temp;
char ch=word.charAt(i);
if(hst.containsKey(ch))
{
temp = hst.get(ch);
temp.add(sc);
}
else
{
temp = new ArrayList<StringWithCount>();
temp.add(sc);
hst.put(ch, temp);
}
}
}
char[] charlist = {'a','b','v','c','m','o','f'};
for(char c : charlist)
{
ArrayList<StringWithCount> tem;
if(hst.containsKey(c))
{
tem=hst.get(c);
for(StringWithCount sc : tem)
{
sc.occurance++;
if(sc.occurance==sc.len)
{
System.out.println(sc.word);
}
}
}
}
}
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class StringWithCount
{
public String word;
public int len;
public int occurance;
public StringWithCount(String w, int l)
{
word=w;
len=l;
occurance=0;
}
}
class Solution
{
public static void main(String[] args)
{
String[] dict = {"meo","got","mov","aaa","cvc","cvf","fbb","wersc"};
Hashtable<Character, ArrayList<StringWithCount>> hst = new Hashtable<>();
for(String word : dict)
{
int len=word.length();
StringWithCount sc = new StringWithCount(word, len);
for(int i=0;i<len;i++)
{
ArrayList<StringWithCount> temp;
char ch=word.charAt(i);
if(hst.containsKey(ch))
{
temp = hst.get(ch);
temp.add(sc);
}
else
{
temp = new ArrayList<StringWithCount>();
temp.add(sc);
hst.put(ch, temp);
}
}
}
char[] charlist = {'a','b','v','c','m','o','f'};
for(char c : charlist)
{
ArrayList<StringWithCount> tem;
if(hst.containsKey(c))
{
tem=hst.get(c);
for(StringWithCount sc : tem)
{
sc.occurance++;
if(sc.occurance==sc.len)
{
System.out.println(sc.word);
}
}
}
}
}
}
Here is how you go about it.
First the theory, and then the ZoomBA dance.
/*
The problem can be solved by first
making the given dictionary a dictionary with :
key -> sorted letters of a word as string
values -> all words who are permutations of the same key
Thus, given an array of letters:
1. we should sort it first.
2. Find all possible sub sequences of the same sorted array
3. For each sub sequence (which would be sorted)
we should check existence as key in the dictionary
and if it does exist, print all words (values) for that key
*/
DICT = [ "go","bat","me","eat","goal", "boy", "run" ]
sorted_dict = mset( DICT ) -> { x = $.o.toCharArray ; sorta( x ) ; str(x,'') }
LETTERS = [ 'e' ,'o' , 'b' ,'a' ,'m' ,'g' , 'l' ]
sorta(LETTERS)
for ( sequences ( LETTERS ) ) {
key = str( $,'')
if( key @ sorted_dict ){
println ( sorted_dict[key] )
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Class1
{
static void Main(string[] args)
{
GetWords();
}
public static void GetWords()
{
char[] charArr = { 'e', 'o', 'b', 'a', 'm', 'g', 'l' };
string[] arryOfWords = { "go", "bat", "me", "eat", "goal", "boy", "run" };
// List<String> listOfWords = new List<string>();
// listOfWords.AddRange(arryOfWords);
List<String> match = new List<String>();
List<string> Words = new List<string>();
foreach (var item in arryOfWords)
{
bool flag = false;
char[] ch = item.ToCharArray();
foreach (var chitem in ch)
{
flag = false;
foreach (var charArrItems in charArr)
{
if (chitem == charArrItems)
{
flag = true;
break;
}
}
}
if (flag)
Words.Add(item);
}
foreach (var item in Words)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Class1
{
static void Main(string[] args)
{
GetWords();
}
public static void GetWords()
{
char[] charArr = { 'e', 'o', 'b', 'a', 'm', 'g', 'l' };
string[] arryOfWords = { "go", "bat", "me", "eat", "goal", "boy", "run" };
// List<String> listOfWords = new List<string>();
// listOfWords.AddRange(arryOfWords);
List<String> match = new List<String>();
List<string> Words = new List<string>();
foreach (var item in arryOfWords)
{
bool flag = false;
char[] ch = item.ToCharArray();
foreach (var chitem in ch)
{
flag = false;
foreach (var charArrItems in charArr)
{
if (chitem == charArrItems)
{
flag = true;
break;
}
}
}
if (flag)
Words.Add(item);
}
foreach (var item in Words)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
}
}
public class Dictionary {
public static void main(String[] args) {
String[] wordsToDic = {"go", "bat", "eat", "goal", "boy", "run","me"};
char[] letters = {'e','o','l','b','a','m','g', '\n'};
Dictionary dic = new Dictionary();
dic.build(wordsToDic);
dic.printAllWordsFromArray(letters);
}
boolean word;
Dictionary[] child;
public Dictionary(){
child = new Dictionary[26];
word = false;
}
private int validChar(int asc) {
if (asc > 96 && asc < 123) {
return asc;
} else if (asc > 64 && asc < 91) {
return asc + 32;
} else {
return -1;
}
}
public void build(String[] words) {
for (String w : words) {
add(w);
}
}
private void add(String w) {
Dictionary current = this;
for (char c : w.toCharArray()) {
if(validChar(c)== -1){
continue;
}
if (current.child[c - 97] == null) {
current.child[c - 97] = new Dictionary();
current = current.child[c - 97];
} else {
current = current.child[c - 97];
}
}
current.word = true;
}
public void printAllWordsFromArray(char[] letters) {
StringBuilder let = new StringBuilder();
for(char c: letters){
if(validChar(c)!= -1){
let.append(c);
}
}
letters = let.toString().toCharArray();
for(char c: letters){
if(child[c-97] != null){
child[c-97].findWords(letters, ""+c);
}
}
}
private void findWords(char[] letters, String string) {
if(word){
System.out.println(string);
}
for(char c:letters){
if(child[c-97]!= null){
child[c-97].findWords(letters, string+c);
}
}
}
}
public class DictionaryWordCheck {
public static void main(String[] args) {
char[] arr = {'e','o','b', 'a','m','g', 'l'};
List<String> strs = new ArrayList<>();
strs.add("go");
strs.add("bat");
strs.add("me");
strs.add("eat");
strs.add("goal");
strs.add("boy");
strs.add("run");
printList(getDictWordsInArray(arr, strs));
}
private static void printList(List<String> dictWordsInArray) {
for (String string : dictWordsInArray) {
System.out.println(string);
}
}
private static List<String> getDictWordsInArray(char[] arr, List<String> strs) {
List<String> results = new ArrayList<>();
HashSet<Character> setChars = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
setChars.add(arr[i]);
}
for (String string : strs) {
char[] chars = string.toCharArray();
int i = 0;
while(i < chars.length && setChars.contains(chars[i])) {
i++;
}
if (i == chars.length) {
results.add(string);
}
}
return results;
}
}
/*
output:
go
me
goal
*/
public static void main(String[] args) {
System.out.println("Valid Words:" + printAllValidWords(new Character[]{'e','o','b','a','m','g','l'}, new HashSet<String>(){{
addAll( Arrays.asList( "go","goa","bat","me","eat","goal","boy","run"));
}}));
}
private static List<String> printAllValidWords( Character [] cArray, Set<String> dictionary ){
Set<Character> charSet = new HashSet<Character>(Arrays.asList( cArray ));
Map<Character, List<String>> charMapping = getWordsStartingFromChar( dictionary );
List<String> validWords = new ArrayList<String>();
for( Character ch: charSet ){
if( charMapping.containsKey( ch )){
List<String> chWords = charMapping.get(ch);
for( String word: chWords ){
char [] wordChar = word.toCharArray();
StringBuffer buffer = new StringBuffer();
for( char c: wordChar ){
if( charSet.contains( c )){
buffer.append( c );
}else {
break;
}
}
if( buffer.toString().equals( word )){
validWords.add( word );
}
}
}
}
return validWords;
}
private static Map<Character, List<String>> getWordsStartingFromChar(Set<String> validWords){
Map<Character, List<String>> charToWord = new HashMap<Character, List<String>>();
for( String word: validWords ){
if( !charToWord.containsKey( word.charAt(0))){
charToWord.put( word.charAt(0), new ArrayList<String>());
}
charToWord.get( word.charAt(0)).add( word );
}
return charToWord;
}
public class StringMatch {
String[] dict = {"go","bat","me","eat","goal", "boy", "run"};
char[] arr = {'e','o','b', 'a','m','g', 'l'};
boolean isPresent(String str) {
//We can implement HashMap as well for this operation
for (String x:dict) {
if(x.equals(str)){
return true;
}
}
return false;
}
void printAllStrings(String larr, String rstr) {
if(larr.length()>0) {
for(int i=0; i<larr.length(); i++) {
String myStr = rstr + larr.charAt(i);
if(this.isPresent(myStr)) {
System.out.println(myStr);
}
printAllStrings(larr.substring(0,i)+larr.substring(i+1,larr.length()),myStr);
}
}
}
public static void main(String[] args) {
StringMatch sm = new StringMatch();
sm.printAllStrings(String.valueOf(sm.arr), "");
}
}
def init
@char_list = ['e','o','b','a','m','g','l']
@string_list = ["go","bat","me","eat","goal","boy","run"]
@char_hash = {}
end
def string_exist(char_hash,string_list,string_sent)
flag = true
string_list.each do |each_string_char|
if char_hash.key?each_string_char then
else
flag = false
print "String is not part of chars : ",string_sent,"\n"
break
end
end
if flag == true then
print "Belong to the list : ",string_sent,"\n"
end
end
def store_chars(char_list,char_hash)
char_list.each do |each_char|
char_hash[each_char] = nil
end
end
init()
store_chars(@char_list,@char_hash)
@string_list.each do |each_string|
string_exist(@char_hash,each_string.split(""),each_string)
end
def init
@char_list = ['e','o','b','a','m','g','l']
@string_list = ["go","bat","me","eat","goal","boy","run"]
@char_hash = {}
end
def string_exist(char_hash,string_list,string_sent)
flag = true
string_list.each do |each_string_char|
if char_hash.key?each_string_char then
else
flag = false
print "String is not part of chars : ",string_sent,"\n"
break
end
end
if flag == true then
print "Belong to the list : ",string_sent,"\n"
end
end
def store_chars(char_list,char_hash)
char_list.each do |each_char|
char_hash[each_char] = nil
end
end
init()
store_chars(@char_list,@char_hash)
@string_list.each do |each_string|
string_exist(@char_hash,each_string.split(""),each_string)
end
<?php
function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}
if($tmp === $str){
return $tmp;
}else{
return null;
}
}
function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];
for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}
init();
?>
function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}
if($tmp === $str){
return $tmp;
}else{
return null;
}
}
function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];
for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}
init();
function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}
if($tmp === $str){
return $tmp;
}else{
return null;
}
}
function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];
for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}
init();
<?php
function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}
if($tmp === $str){
return $tmp;
}else{
return null;
}
}
function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];
for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}
init();
?>
<?php
function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}
if($tmp === $str){
return $tmp;
}else{
return null;
}
}
function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];
for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}
init();
?>
import java.util.Scanner;
class dictionary{
public static void main(String[]args){
Scanner scan=new Scanner(System.in);
String[] temp=new String[10];
char[] arr={'e','o', 'b', 'a', 'm', 'g', 'l'};
String[] Dict={"go","bat","me","eat","goal","boy","run"};
int val=0,k=0,len=0;
for(int i=0;i<7;i++)
{
val=0;
for(int j=0;j<7;j++)
{
len=Dict[i].length();
if(Dict[i].contains((arr[j]+"")))
{
val++;
}
}
if(val==len)
{
temp[k]=Dict[i];
len=0;
k++;
}
}
for(int i=0;i<k;i++)
{
System.out.println(temp[i]);
}
}
}
class Program
{
static void Main(string[] args)
{
string[] dic = {"go", "bat", "me", "eat", "goal", "boy", "run"};
char[] arr = { 'e', 'o', 'b', 'm', 'a', 'g', 'l' };
foreach(var item in dic)
{
bool print = true;
foreach(var c in item)
{
if(!arr.Contains(c))
{
print = false;
}
}
if(print)
Console.WriteLine(item);
}
Console.ReadLine();
}
}
Please suggest changes if any :
import java.util.*;
public class Dictionary {
static Map<String, String> test = new TreeMap<>();
public static void main(String[] args) {
long startTime = new Date().getTime();
char []arr = {'e','o','b','a','m','g','l'};
int min_length, max_length = 4;
List<String> dict = new ArrayList<>();
dict.add("go");
dict.add("bat");
dict.add("me");
dict.add("eat");
dict.add("goal");
dict.add("boy");
dict.add("run");
List<String> output = new ArrayList<>();
for(min_length=2;min_length<=max_length;min_length++){
possibleStrings(min_length, arr,"");
}
for(String dictionaryWord : dict){
if(test.containsKey(dictionaryWord))
output.add(dictionaryWord);
}
for(int i=0;i<output.size();i++){
System.out.print(output.get(i)+" ");
}
long endTime = new Date().getTime();
System.out.println();
System.out.println("Time taken : "+(endTime-startTime));
}
public static void possibleStrings(int maxLength, char[] alphabet, String curr) {
// If the current string has reached it's maximum length
if (curr.length() == maxLength) {
test.put(curr, curr);
// Else add each letter from the alphabet to new strings and process
// these new strings again
} else {
for (int i = 0; i < alphabet.length; i++) {
String oldCurr = curr;
curr += alphabet[i];
possibleStrings(maxLength, alphabet, curr);
curr = oldCurr;
}
}
}
}
List<String> formValidWords(List<String> dict, char[] givenChar)
{ int[] avail = new int[26]; //assuming givenChar contains only alphabets a-z
for(char c:givenChar)
avail[c-'a']++;
List<String> result = new ArrayList<String>();
for(String word: dict)
{ int[] count = new int[26];
boolean flag = true;
for(char c: word.toCharArray)
{ count[c-'a']++;
if(count[c-'a'] > avail[c-'a'])
{ flag = false;
break;
} }
if(flag) result.add(word);
}
return result;
}
public class S1 {
public static void main(String[] args) {
char a[] = {'e' ,'b' ,'o','a','m','g','l'};
String[] a1 ={"go","bat","me","eat","goal","boy","run"};
for (int i = 0; i < a1.length; i++) {
int count =0;
String s1= a1[i] ;
for (int j = 0; j < s1.length(); j++) {
for (int j2 = 0; j2 < a.length; j2++) {
if (s1.charAt(j) == a[j2]) {
count++;
if(count == s1.length()){
System.out.println(s1);
}
}
}
}
}
}
}
public class S1 {
public static void main(String[] args) {
char a[] = {'e' ,'b' ,'o','a','m','g','l'};
String[] a1 ={"go","bat","me","eat","goal","boy","run"};
for (int i = 0; i < a1.length; i++) {
int count =0;
String s1= a1[i] ;
for (int j = 0; j < s1.length(); j++) {
for (int j2 = 0; j2 < a.length; j2++) {
if (s1.charAt(j) == a[j2]) {
count++;
if(count == s1.length()){
System.out.println(s1);
}
}
}
}
}
}
}
An easier approach is to precompute a map of sorted characters for each word in the dictionary. Also, sort the char array. This would allow us to find solution linearly.
private static List<String> possibleWords(char[] chars, String[] wordDict) {
List<String> possibleWords = new LinkedList<>();
Arrays.sort(chars);
Map<String, char[]> wordToSortedCharMap = getWordToSortedCharsMap(wordDict);
for(Map.Entry<String, char[]> entry: wordToSortedCharMap.entrySet()){
char[] wordChars = entry.getValue();
for(int i=0, j=0; i<chars.length && j<wordChars.length;){
if(chars[i]==wordChars[j]){
j++;
//i++;//if no repetition allowed
} else {
i++;
}
if(j == wordChars.length){//i.e. all chars matched
possibleWords.add(entry.getKey());
}
}
}
return possibleWords;
}
private static Map<String, char[]> getWordToSortedCharsMap(String[] list){
Map<String, char[]> map = new HashMap<>();
for(String word: list){
char[] chars = word.toCharArray();
Arrays.sort(chars);
map.put(word, chars);
}
return map;
}
public static void main(String[] args){
char[] chars = {'e','o','b', 'a','m','g', 'l'};
String[] dict = {"go","bat","me","eat","goal", "boy", "run"};
System.out.println(possibleWords(chars, dict));
}
I have used Hashing to find the solution
static void printWords(char[] arr, String[] dict) {
HashSet<Character> hs = new HashSet<Character>();
int i;
for(i =0;i<arr.length;i++)
hs.add(arr[i]);
for(String s: dict){
for(i =0;i<s.length();i++) {
if(hs.contains(s.charAt(i)))
continue;
else
break;
}
if(i == s.length()) // match found
System.out.println(s);
}
}
import java.util.ArrayList;
public class DictionaryWordCheck {
/*
* Given dictionary and a char arr, print all the valid words
* that are possible using char from the array.
*
* Ex- char[] arr = {'e','o','b','a','m','g','i'}
* Dict - {"go","bat","me","eat","goal","boy","run"}
* Print - go, me, goal
*/
static ArrayList printAllValidWords(char[] arr, String dictionary[]) {
ArrayList<String> validWords = new ArrayList<>();
for(int i = 0; i<dictionary.length; i++) {
//Get the length of the dictionary word//
int wordLength = dictionary[i].length();
int characterCount = 0;
for(int j = 0; j<arr.length; j++) {
//check if character is in dictionary word//
int Index = (dictionary[i]).indexOf(arr[j]);
if (Index > -1) {
//if character is in the dictionary word, increment the character count//
characterCount++;
}
}
//check if dictionary word length is equal to character count//
if(wordLength == characterCount) {
/*if the count is the same as length of dictionary word,
add the dictionary word to the validWords list
- The characters can be re-shuffled to spell the dictionary word*/
validWords.add(dictionary[i]);
}
}
return validWords;
}
static String arrayList2String(ArrayList<String> validWordsList) {
StringBuilder sb = new StringBuilder();
// Appends characters one by one
for (String ch : validWordsList) {
sb.append(ch).append(", ");
}
String validWords = sb.deleteCharAt(sb.length() - 2).toString();
return validWords;
}
public static void main(String args[]) {
char[] arr = {'e','o','b','a','m','g','l'};
String dictionary[] = {"go","bat","me","eat","goal","boy","run"};
ArrayList<String> validWords = printAllValidWords(arr, dictionary);
System.out.println(arrayList2String(validWords));
}
}
import java.util.ArrayList;
public class DictionaryWordCheck {
/*
* Given dictionary and a char arr, print all the valid words
* that are possible using char from the array.
*
* Ex- char[] arr = {'e','o','b','a','m','g','i'}
* Dict - {"go","bat","me","eat","goal","boy","run"}
* Print - go, me, goal
*/
static ArrayList printAllValidWords(char[] arr, String dictionary[]) {
ArrayList<String> validWords = new ArrayList<>();
for(int i = 0; i<dictionary.length; i++) {
//Get the length of the dictionary word//
int wordLength = dictionary[i].length();
int characterCount = 0;
for(int j = 0; j<arr.length; j++) {
//check if character is in dictionary word//
int Index = (dictionary[i]).indexOf(arr[j]);
if (Index > -1) {
//if character is in the dictionary word, increment the character count//
characterCount++;
}
}
//check if dictionary word length is equal to character count//
if(wordLength == characterCount) {
/*if the count is the same as length of dictionary word,
add the dictionary word to the validWords list
- The characters can be re-shuffled to spell the dictionary word*/
validWords.add(dictionary[i]);
}
}
return validWords;
}
static String arrayList2String(ArrayList<String> validWordsList) {
StringBuilder sb = new StringBuilder();
// Appends characters one by one
for (String ch : validWordsList) {
sb.append(ch).append(", ");
}
String validWords = sb.deleteCharAt(sb.length() - 2).toString();
return validWords;
}
public static void main(String args[]) {
char[] arr = {'e','o','b','a','m','g','l'};
String dictionary[] = {"go","bat","me","eat","goal","boy","run"};
ArrayList<String> validWords = printAllValidWords(arr, dictionary);
System.out.println(arrayList2String(validWords));
}
}
import java.util.ArrayList;
public class DictionaryWordCheck {
/*
* Given dictionary and a char arr, print all the valid words
* that are possible using char from the array.
*
* Ex- char[] arr = {'e','o','b','a','m','g','i'}
* Dict - {"go","bat","me","eat","goal","boy","run"}
* Print - go, me, goal
*/
static ArrayList printAllValidWords(char[] arr, String dictionary[]) {
ArrayList<String> validWords = new ArrayList<>();
for(int i = 0; i<dictionary.length; i++) {
//Get the length of the dictionary word//
int wordLength = dictionary[i].length();
int characterCount = 0;
for(int j = 0; j<arr.length; j++) {
//check if character is in dictionary word//
int Index = (dictionary[i]).indexOf(arr[j]);
if (Index > -1) {
//if character is in the dictionary word, increment the character count//
characterCount++;
}
}
//check if dictionary word length is equal to character count//
if(wordLength == characterCount) {
/*if the count is the same as length of dictionary word,
add the dictionary word to the validWords list
- The characters can be re-shuffled to spell the dictionary word*/
validWords.add(dictionary[i]);
}
}
return validWords;
}
static String arrayList2String(ArrayList<String> validWordsList) {
StringBuilder sb = new StringBuilder();
// Appends characters one by one
for (String ch : validWordsList) {
sb.append(ch).append(", ");
}
String validWords = sb.deleteCharAt(sb.length() - 2).toString();
return validWords;
}
public static void main(String args[]) {
char[] arr = {'e','o','b','a','m','g','l'};
String dictionary[] = {"go","bat","me","eat","goal","boy","run"};
ArrayList<String> validWords = printAllValidWords(arr, dictionary);
System.out.println(arrayList2String(validWords));
}
}
import java.util.ArrayList;
public class DictionaryWordCheck {
/*
* Given dictionary and a char arr, print all the valid words
* that are possible using char from the array.
*
* Ex- char[] arr = {'e','o','b','a','m','g','i'}
* Dict - {"go","bat","me","eat","goal","boy","run"}
* Print - go, me, goal
*/
static ArrayList printAllValidWords(char[] arr, String dictionary[]) {
ArrayList<String> validWords = new ArrayList<>();
for(int i = 0; i<dictionary.length; i++) {
//Get the length of the dictionary word//
int wordLength = dictionary[i].length();
int characterCount = 0;
for(int j = 0; j<arr.length; j++) {
//check if character is in dictionary word//
int Index = (dictionary[i]).indexOf(arr[j]);
if (Index > -1) {
//if character is in the dictionary word, increment the character count//
characterCount++;
}
}
//check if dictionary word length is equal to character count//
if(wordLength == characterCount) {
/*if the count is the same as length of dictionary word,
add the dictionary word to the validWords list
- The characters can be re-shuffled to spell the dictionary word*/
validWords.add(dictionary[i]);
}
}
return validWords;
}
static String arrayList2String(ArrayList<String> validWordsList) {
StringBuilder sb = new StringBuilder();
// Appends characters one by one
for (String ch : validWordsList) {
sb.append(ch).append(", ");
}
String validWords = sb.deleteCharAt(sb.length() - 2).toString();
return validWords;
}
public static void main(String args[]) {
char[] arr = {'e','o','b','a','m','g','l'};
String dictionary[] = {"go","bat","me","eat","goal","boy","run"};
ArrayList<String> validWords = printAllValidWords(arr, dictionary);
System.out.println(arrayList2String(validWords));
}
}
import java.util.ArrayList;
public class DictionaryWordCheck {
/*
* Given dictionary and a char arr, print all the valid words
* that are possible using char from the array.
*
* Ex- char[] arr = {'e','o','b','a','m','g','i'}
* Dict - {"go","bat","me","eat","goal","boy","run"}
* Print - go, me, goal
*/
static ArrayList printAllValidWords(char[] arr, String dictionary[]) {
ArrayList<String> validWords = new ArrayList<>();
for(int i = 0; i<dictionary.length; i++) {
//Get the length of the dictionary word//
int wordLength = dictionary[i].length();
int characterCount = 0;
for(int j = 0; j<arr.length; j++) {
//check if character is in dictionary word//
int Index = (dictionary[i]).indexOf(arr[j]);
if (Index > -1) {
//if character is in the dictionary word, increment the character count//
characterCount++;
}
}
//check if dictionary word length is equal to character count//
if(wordLength == characterCount) {
/*if the count is the same as length of dictionary word,
add the dictionary word to the validWords list
- The characters can be re-shuffled to spell the dictionary word*/
validWords.add(dictionary[i]);
}
}
return validWords;
}
static String arrayList2String(ArrayList<String> validWordsList) {
StringBuilder sb = new StringBuilder();
// Appends characters one by one
for (String ch : validWordsList) {
sb.append(ch).append(", ");
}
String validWords = sb.deleteCharAt(sb.length() - 2).toString();
return validWords;
}
public static void main(String args[]) {
char[] arr = {'e','o','b','a','m','g','l'};
String dictionary[] = {"go","bat","me","eat","goal","boy","run"};
ArrayList<String> validWords = printAllValidWords(arr, dictionary);
System.out.println(arrayList2String(validWords));
}
ZoomBA Guy (NoOne):
I don't think this is the most efficient way in this case. I believe the # of possible permutations of sorted characters grows at a faster rate as length of character array increases (n!) than the dictionary likely would (which probably has max 50,60,100K words).
I propose this, which is O(p*(n +m)) where p is the length of the dictionary, n is the length of the character array, and m is the average word length of the dictionary.
- srterpe December 07, 2016function valid (chars, dict) { var spellables = [] for (var j = 0; j < dict.length; ++j) { var map = {} for (var i = 0; i < chars.length; ++i) { if (map[chars[i]]) { map[chars[i]] += 1 } else { map[chars[i]] = 1 } } var bool = true for (var k = 0; k < dict[j].length; ++k) { if (!map[dict[j].charAt(k)]) { bool = false break } else { map[dict[j].charAt(k)]-- } } if (bool) { spellables.push(dict[j]) } } console.log(spellables) } valid(['e', 'o', 'b', 'a', 'm', 'g', 'l'], [ 'go', 'bat', 'me', 'eat', 'goal', 'boy', 'run' ]);