Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
class Program
{
static void Main(string[] args)
{
List<string> dict = new List<string>();
dict.Add("ale");
dict.Add("apple");
dict.Add("monkey");
dict.Add("plea");
String input = "abpcplea";
List<string> dict1 = new List<string>();
LongestStringAfterCharacterDelete ls = new LongestStringAfterCharacterDelete();
dict1=ls.findLongestString(dict, input);
string nik= dict1.Aggregate("", (max, cur) => max.Length > cur.Length ? max : cur);
Console.WriteLine(nik);
Console.ReadLine();
}
public class LongestStringAfterCharacterDelete
{
public List<string> findLongestString(List<string> dict, string input)
{
StringBuilder Finalstring = new StringBuilder();
StringBuilder final = new StringBuilder();
Finalstring.Append(input);
int index=0;
List<String> multipleLongestString = new List<String>();
foreach (var nik in dict)
{
foreach (char c in nik)
{
if ((Finalstring.ToString()).ToLower().Contains(c))
{
index = (Finalstring.ToString()).IndexOf(c);
Finalstring = Finalstring.Remove(index, 1);
final.Append(c);
}
else
{
final.Clear();
break;
}
}
multipleLongestString.Add(final.ToString());
final.Clear();
Finalstring.Clear();
Finalstring.Append(input);
}
return multipleLongestString;
}
}
}
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LargestSubsequence {
public static String solve(String s, List<String> words) {
Map<Character, List<Integer>> charIndexMap = new HashMap<>();
words.sort(new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
List<Integer> indexList;
if ((indexList = charIndexMap.get(letter)) != null) {
indexList.add(i);
} else {
indexList = new ArrayList<>();
indexList.add(i);
charIndexMap.put(letter, indexList);
}
}
String result = null;
for (String word : words) {
boolean found = false;
for (int i = 0; i < word.length(); i++) {
char letter = word.charAt(i);
boolean letterFound = false;
if (charIndexMap.get(letter) == null) {
letterFound = false;
found = false;
break;
} else {
List<Integer> indices = charIndexMap.get(letter);
for (int index : indices) {
if (index >= i) {
letterFound = true;
break;
}
}
}
if (!letterFound) {
found = false;
break;
} else {
found = true;
}
}
if (found) {
result = word;
break;
}
}
return result;
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
printLongestWord("abpcplea",new HashSet(Arrays.asList("ale", "apple", "monkey", "plea")));
}
public static void printLongestWord(String input, Set<String> dictonary){
Set<String> sortedBySizeDictonary = orderSetBySize(dictonary);
for (String dictonaryEntire : sortedBySizeDictonary) {
if (isStringContained(dictonaryEntire, input)) {
System.out.println(dictonaryEntire);
return;
}
}
}
public static boolean isStringContained(String src, String dest){
int i=0,j=0;
while (j<dest.length() && i<src.length()){
char x=src.charAt(i);
char y=dest.charAt(j);
if (x==y) {
i++;
}
j++;
if (!(j<dest.length())){
return false;
}
}
return true;
}
private static Set<String> orderSetBySize(Set<String> set) {
TreeSet<String> treeSet= new TreeSet(new comparator());
for (String entire : set){
treeSet.add(entire);
}
return treeSet;
}
static class comparator implements Comparator<String>{
@Override
public int compare(String s, String t1) {
if (s.length()>t1.length()) return -1;
return 1;
}
}
There are three approaches: 1) Trie of words in the dictionary + dfs on the query string. Time complexity: O(max(w*m,n^2)) Space is O(w*m) where n is the length of the query string w is the length of the longest word and m is the length o the dictionary. 2) Find the lcs between each word in the dictionary and the query string.Time: O(w*m*n) Space:O(min(w,n)) 3)Using a single while loop and two pointers (i-characters in a word, j-characters in query string) determine if word occurs in query string. Time: O(w*m*n) Space:O(1)
There are three approaches: 1) Trie of words in the dictionary + dfs on the query string. Time complexity: O(max(w*m,n^2)) Space is O(w*m) where n is the length of the query string w is the length of the longest word and m is the length o the dictionary. 2) Find the lcs between each word in the dictionary and the query string.Time: O(w*m*n) Space:O(min(w,n)) 3)Using a single while loop and two pointers (i-characters in a word, j-characters in query string) determine if word occurs in query string. Time: O(w*m*n) Space:O(1)
function longestString(str,dict){
var longestStr = '';
if(!str) return;
if (dict.indexOf(str) > -1) return str;
function getLongest(str){
var i=0;
if (str.length < longestStr.length) return longestStr;
while (i<str.length){
var s1 = str.substr(0,i).concat(str.substr(i+1,str.length-i));
if (dict.indexOf(s1)>-1){
return s1;
}
i++;
}
var j=0;
while (j<str.length){
var s2 = str.substr(0,j).concat(str.substr(j+1,str.length-j));
var ls = getLongest(s2);
longestStr = (ls && ls.length > longestStr.length) ? ls : longestStr ;
j++;
}
return longestStr;
}
return getLongest(str);
}
console.log(longestString("abpcplebaee",["ale","apple","monkey","plea","applebee"]));
console.log(longestString("abpcplea",["ale","apple","monkey","plea"]));
Maybe I suck at coding but I would probably not be able to build a Trie on command and I am also not certain it would be expected (although maybe nice) in a phone interview. Since this is a phone interview question I created something simple which solves the problem but can provide discussion on how it can be improved.
If you are doing an interview just know that working but simple is better than not working but complicated.
public static String longest(ArrayList<String> dict, String inputString){
String retVal ="";
for(String s:dict){
StringBuffer check = new StringBuffer();
int sIndex=0, inputIndex=0;
while(sIndex<s.length() &&inputIndex<inputString.length()){
if(s.charAt(sIndex)==inputString.charAt(inputIndex)){
check.append(s.charAt(sIndex));
sIndex++;
inputIndex++;
}else{
inputIndex++;
}
}
if (check.toString().equals(s)){
if(s.length() > retVal.length()){
retVal=s;
}
}
}
return retVal;
}
public class LongestStringInDictionary {
public static class Trie {
char current;
Trie[] nextChars = new Trie[26];
boolean isWord = false;
public Trie(char current) {
this.current = current;
}
}
public static class Dictionary {
Trie root = new Trie('*');
public void addWord(String s) {
Trie currentNode = root;
for (int i=0; i < s.length(); ++i) {
char c = s.charAt(i);
Trie newLetter = currentNode.nextChars[c - 'a'];
if (newLetter == null) {
newLetter = new Trie(c);
currentNode.nextChars[c - 'a'] = newLetter;
}
currentNode = newLetter;
}
currentNode.isWord = true;
}
public boolean isWord(String s) {
Trie prefix = getPrefix(s);
return (s == null) ? false : prefix.isWord;
}
public boolean isPrefix(String s) {
Trie prefix = getPrefix(s);
return (prefix != null);
}
private Trie getPrefix(String s) {
Trie currentNode = root;
int length = 0;
boolean isFound = true;
for (int i=0; (i < s.length()) && isFound; ++i) {
char c = s.charAt(i);
Trie newLetter = currentNode.nextChars[c - 'a'];
if (newLetter != null) {
++length;
} else {
isFound = false;
}
currentNode = newLetter;
}
if (isFound && (length == s.length())) {
return currentNode;
} else {
return null;
}
}
}
public String getLongestValidWord(String prefix, String remaining, Dictionary root) {
String maxStr = null;
for (int i=0; i< remaining.length(); ++i) {
char c = remaining.charAt(i);
if (root.isPrefix(prefix + c)) {
if (root.isWord(prefix + c) && ((maxStr == null) || (maxStr.length() < (prefix.length() + 1)))) {
maxStr = prefix + c;
}
String newRemaining = remaining.substring(0,i) + remaining.substring (i + 1, remaining.length());
String logestWithC = getLongestValidWord(prefix + c, newRemaining, root);
if ((logestWithC != null) && ((maxStr == null) || (maxStr.length() < logestWithC.length()))) {
maxStr = logestWithC;
}
}
}
return maxStr;
}
public String getLongestValidWord(String s, Dictionary root) {
return getLongestValidWord("", s, root);
}
public static void main(String args[]) {
Dictionary d = new Dictionary();
d.addWord("apl");
d.addWord("apple");
d.addWord("monkey");
d.addWord("plea");
System.out.println((new LongestStringInDictionary()).getLongestValidWord("abpcplea", d));
}
}
Recursive Python solution
def longest_st(S, slist, longest=''):
if S in slist and len(S)>len(longest):
return S
else:
for i in range(len(S)):
longest = longest_st(S[:i]+S[i+1:], slist, longest)
return longest
In [1]: longest_st('abpcplea', ['ale', 'apple', 'monkey', 'plea'])
Out[1]: 'apple'
package practice;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Created by Mythri on 2/3/17.
*/
public class LongestStringDict {
public String LongestWord(List<String> dict, String s){
int max_len = 0;
Stack<String> lword = new Stack<>();
for(String word : dict){
boolean flag = true;
char[] charArray = word.toCharArray();
for(char c: charArray){
if(flag){
if(!s.contains(c+"")){
flag = false;
}
}
}
if(flag && max_len <= word.length()){
max_len = word.length();
lword.push(word);
}
}
return lword.pop();
}
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("ale");
list.add("apple");
list.add("monkey");
list.add("plea");
String s = "abpcplea";
LongestStringDict obj = new LongestStringDict();
System.out.println(obj.LongestWord(list,s));
}
}
package practice;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Created by Mythri on 2/3/17.
*/
public class LongestStringDict {
public String LongestWord(List<String> dict, String s){
int max_len = 0;
Stack<String> lword = new Stack<>();
for(String word : dict){
boolean flag = true;
char[] charArray = word.toCharArray();
for(char c: charArray){
if(flag){
if(!s.contains(c+"")){
flag = false;
}
}
}
if(flag && max_len <= word.length()){
max_len = word.length();
lword.push(word);
}
}
return lword.pop();
}
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("ale");
list.add("apple");
list.add("monkey");
list.add("plea");
String s = "abpcplea";
LongestStringDict obj = new LongestStringDict();
System.out.println(obj.LongestWord(list,s));
}
}
public static String _longestString (String[] dictionary, String input) {
String answer = null;
for (String item : dictionary) {
String lcs = longestCommonSubstring(item, input);
if (answer == null || lcs.length() > answer.length())
answer = lcs;
}
return answer;
}
private static String longestCommonSubstring (String a, String b) {
int[][] dp = new int [a.length() + 1][b.length() + 1];
int maxLength = 0;
for (int row = 0; row < a.length(); row ++) {
for (int col = 0; col < b.length(); col ++) {
if (a.charAt(row) == b.charAt(col))
dp [row + 1][col + 1] = dp [row][col] + 1;
else
dp [row + 1][col + 1] = Math.max(dp [row][col + 1], dp [row + 1][col]);
maxLength = Math.max(maxLength, dp [row + 1][col + 1]);
}
}
char[] answer = new char [maxLength];
int idx = answer.length - 1, row = dp.length - 1, col = dp[0].length - 1;
while (row > 0 && col > 0) {
if (dp [row][col] == dp [row - 1][col]) { row --; continue; }
if (dp [row][col] == dp [row][col - 1]) { col --; continue; }
answer [idx --] = a.charAt(row - 1);
row --; col --;
}
return String.valueOf (answer);
}
public static String _longestString (String[] dictionary, String input) {
String answer = null;
for (String item : dictionary) {
String lcs = longestCommonSubstring(item, input);
if (answer == null || lcs.length() > answer.length())
answer = lcs;
}
return answer;
}
private static String longestCommonSubstring (String a, String b) {
int[][] dp = new int [a.length() + 1][b.length() + 1];
int maxLength = 0;
for (int row = 0; row < a.length(); row ++) {
for (int col = 0; col < b.length(); col ++) {
if (a.charAt(row) == b.charAt(col))
dp [row + 1][col + 1] = dp [row][col] + 1;
else
dp [row + 1][col + 1] = Math.max(dp [row][col + 1], dp [row + 1][col]);
maxLength = Math.max(maxLength, dp [row + 1][col + 1]);
}
}
char[] answer = new char [maxLength];
int idx = answer.length - 1, row = dp.length - 1, col = dp[0].length - 1;
while (row > 0 && col > 0) {
if (dp [row][col] == dp [row - 1][col]) { row --; continue; }
if (dp [row][col] == dp [row][col - 1]) { col --; continue; }
answer [idx --] = a.charAt(row - 1);
row --; col --;
}
return String.valueOf (answer);
}
___QUESTIONS___
Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
this can be solved in nlogn time complexity with O(n) extra space
step 1-
Insert the string S in Map<C,I> where C is the character present in S and I is its corresponding frequency.
step 2-
now sort the dictionary in decreasing order and check for words in it ....if all the characters present in the word is also present in the S , then S can be converted into that word .
Simple approach
public class LongestString {
public static void main(String[] args) {
String[] dict = { "ale", "apple", "monkey", "plea" };
String word = "abpcplea";
String longestWord = longestWord(dict, word);
System.out.println(longestWord);
}
private static String longestWord(String[] dict, String word) {
String lastWord = "";
boolean[] wArr = new boolean[128];
char[] wChars = word.toCharArray();
for (int i = 0; i < wChars.length; i++) {
wArr[wChars[i]] = Boolean.TRUE;
}
for (String dictWord : dict) {
char[] dChars = dictWord.toCharArray();
boolean add = true;
for (char c : dChars) {
if (!wArr[c]) {
add = false;
break;
}
}
if (add) {
if (dictWord.length() > lastWord.length()) {
lastWord = dictWord;
}
}
}
return lastWord;
}
}
Simple approach
complexity : O(K*N)
K= Number of words in dict
N = length of dict word
Space : constant
public class LongestString {
public static void main(String[] args) {
String[] dict = { "ale", "apple", "monkey", "plea" };
String word = "abpcplea";
String longestWord = longestWord(dict, word);
System.out.println(longestWord);
}
private static String longestWord(String[] dict, String word) {
String lastWord = "";
boolean[] wArr = new boolean[128];
char[] wChars = word.toCharArray();
for (int i = 0; i < wChars.length; i++) {
wArr[wChars[i]] = Boolean.TRUE;
}
for (String dictWord : dict) {
char[] dChars = dictWord.toCharArray();
boolean add = true;
for (char c : dChars) {
if (!wArr[c]) {
add = false;
break;
}
}
if (add) {
if (dictWord.length() > lastWord.length()) {
lastWord = dictWord;
}
}
}
return lastWord;
}
}
package Strings;
import java.util.HashSet;
import java.util.Hashtable;
/**
* Created by Anusha on 2/12/2017.
*/
public class stringDictionary {
public static boolean contains(String dictString,String inputString){
int idx1=0,idx2=0;
while(idx1<dictString.length() && idx2<inputString.length()){
if(dictString.charAt(idx1)==inputString.charAt(idx2)){
idx1++;
idx2++;
}
else{
idx2++;
}
}
if(idx1==dictString.length()) return true;
else return false;
}
public static void getLongestString(HashSet<String> dict, String input){
String result="";
for(String str : dict){
if(contains(str,input) && result.length()<str.length())
result=str;
}
System.out.println(result);
}
public static void main(String[] args){
HashSet<String> dict=new HashSet<String>();
dict.add("ale");
dict.add("apple");
dict.add("monkey");
dict.add("plea");
String input=new String("ambponcpkleya");
getLongestString(dict,input);
}
}
static String longestStr = "";
public static String findLongestSubsequence(String[] dicts,String target){
TrieNode root = buildTrieTree(dicts);
char[] array = target.toCharArray();
Map<Character,TreeSet<Integer>> map = new HashMap<>();
for(int i=0;i<array.length;i++){
if(!map.containsKey(array[i])){
map.put(array[i],new TreeSet<>());
}
map.get(array[i]).add(i);
}
longestSubseqSearch(root,map,0);
return longestStr;
}
public static void longestSubseqSearch(TrieNode root,Map<Character,TreeSet<Integer>> map,
int pos){
if(root==null){
return;
}
if(root.str!=null){
if((root.str).length()>longestStr.length()){
longestStr = root.str;
}
}
for(int i=0;i<26;i++){
if(root.childs[i]==null){
continue;
}
char c = (char)(i+'a');
if(!map.containsKey(c)){
continue;
}
TreeSet<Integer> temp_set = map.get(c);
Integer index = temp_set.ceiling(pos);
if(index==null){
continue;
}else{
longestSubseqSearch(root.childs[i],map,index+1);
}
}
}
public static TrieNode buildTrieTree(String[] dicts){
TrieNode root = new TrieNode();
for(String str:dicts){
TrieNode current = root;
char[] array = str.toCharArray();
for(int i=0;i<array.length;i++){
char c = array[i];
if(current.childs[c-'a']==null){
current.childs[c-'a'] = new TrieNode();
}
current = current.childs[c-'a'];
}
current.str = str;
}
return root;
}
public class Subseq {
public static void main(String[] args) {
String s = "abppplee", s1=""; int k = 0;
String[] ss = {"able", "ale", "apple", "bale", "kangaroo"};
int[] n = new int[ss.length];
for(int i = 0; i < ss.length; i++){
k = 0;s1="";
for(int j = 0; j < ss[i].length(); j++){
int c = 0;
for( ; k < s.length(); k++){
if(ss[i].charAt(j) == s.charAt(k)){
s1 += ss[i].charAt(j);
break;
}
}
}
n[i] = s1.length();
}
k=1;
for(int i=0; i<n.length; i++){
//System.out.println(ss[i]);
k=1;
for(int j=0;j<n.length;j++){
if(n[i] < n[j]){
k=0;
}
}
if(k==1){
System.out.println(ss[i]);
}
}
}
}
O(N*n*k)
def find(S, D):
last = ["", 0] # [subsequence, length]
for W in D:
lPos = -1
isSub = True
for j in W:
cPos = S.find(j, lPos+1)
if(cPos != -1):
lPos = cPos
else:
isSub = False
break
if(isSub):
cLen = len(W)
if(last[1] < cLen):
last[0] = W
last[1] = cLen
return last[0]
print(find("abppplee", ["able", "ale", "apple", "bale", "kangaroo"]))
public static void main(String[] args) {
Trie root = createRoot();
add(root, "ale");
add(root, "apple");
add(root, "monkey");
add(root, "plea");
String search = "sdfmsdrodrsnksrtsegdygee";
String[] maxstr = { "" };
max(root, search, 0, Integer.MIN_VALUE, "", maxstr);
System.out.println(maxstr[0]);
}
// Giving a string and an string dictionary, find the longest string in
// dictionary which can formed by deleting some characters of the giving
// string.
// eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
public static int max(Trie node, String search, int i, int maxLen, String str, String[] maxStr) {
int n = search.length() - 1;
if (node == null)
return maxLen;
if(i > n+1)
return maxLen;
if (node.isEnd && str.length() > maxLen) {
maxLen = str.length();
maxStr[0] = str;
}
for (int k = i; k <= n; k++) {
if (node != null && node.next != null && node.next.val[search.charAt(k) - 'a'] > 0)
maxLen = max(node.next, search, k + 1, maxLen, str + search.charAt(k), maxStr);
}
return maxLen;
}
// apple
public static void add(Trie root, String str) {
char[] carr = str.toCharArray();
int i = 0;
Trie node = root;
while (i < carr.length) {
Trie t = node.next;
if (t == null) {
t = new Trie();
node.next = t;
}
t.val[carr[i] - 'a'] = 1;
if (i == carr.length - 1)
t.isEnd = true;
i++;
node = node.next;
}
}
public static Trie createRoot() {
return new Trie();
}
static class Trie {
Trie next;
int[] val = new int[26];
boolean isEnd;
}
Java solution, should be clean and quick
String find(String keyword, String[] dict){
String longest="";
for(String word:dict){
if(word.length()<=keyword.length()&&word.length()>longest.length()){
int i=0, insert=0;
boolean isSub=false;
while(insert+word.length()<=keyword.length()){
if(word.charAt(i)==keyword.charAt(i+insert)){
i++;
if(i==word.length()){
isSub=true;
break;
}
}
else insert++;
}
if(isSub) longest=word;
}
}
return longest;
}
O(N*L),
N: number of characters in S,
L: number of total characters in D
def find_longest_subsequence_v1(S, D):
""" Greedy Algorithm """
D = sorted(D, key=len, reverse=True)
for word in D:
i = j = 0
while True:
try:
i = S[i:].index(word[j]) + i
j+=1
except ValueError:
break
except IndexError:
return word
/* Simplest way of doing this*/
public class LongestDictionaryWord {
public static void main(String a[])
{
String s1 = "abppplee";
String[] s2= {"able", "ale", "apple", "bale", "kangaroo"};
int count[] = new int[100];
int ccheck[] = new int[100];
for(int i=0;i<100;i++)
{
count[i] = 0;
ccheck[i] = 0;
}
for (int k=0; k<s2.length;k++)
{
count[k] = s2[k].length();
for(int q=0;q<s2[k].length();q++)
{
for(int j=0;j<s1.length();j++)
{
if(s1.charAt(j)== s2[k].charAt(q))
{
ccheck[k] = ccheck[k]+1;
//System.out.println(s1.charAt(q)+ "\t Found");
break;
}
}
}
}
int temp;
for(int y=0;y<ccheck.length - 1;y++)
{
for(int z=1;z<ccheck.length - 1;z++)
{
if(ccheck[y]<ccheck[z])
{
temp = ccheck[y];
ccheck[y] = ccheck[z];
ccheck[z]=temp;
}
}
}
for (int l=0; l<s2.length;l++)
{
if(ccheck[0] == s2[l].length())
{
//System.out.println(ccheck[0]);
System.out.println(s2[l] +"\t string is the largest substring of \t"+s1);
continue;
}
}
}
}
package com.anand.test;
import java.util.ArrayList;
import java.util.List;
public class LongestSubSeqSol {
public static void main(String[] args) {
List<String> dictionary = new ArrayList<>();
dictionary.add("able");
dictionary.add("ale");
dictionary.add("apple");
dictionary.add("bale");
dictionary.add("kangaroo");
String searchStr = "abppplee";
String output = getLongestSubsequence(dictionary, searchStr);
System.out.println(output);
}
private static String getLongestSubsequence(List<String> dictionary, String searchStr) {
dictionary.sort((s1, s2) -> s2.length() - s1.length());
String output = "******Not Found*****";
for (String word : dictionary) {
if (checkSubsequence(word, searchStr)) {
output = word;
break;
}
}
return output;
}
private static boolean checkSubsequence(String word, String searchStr) {
int j = 0;
for (int i = 0; i < searchStr.length(); i++) {
if (j < word.length() && word.charAt(j) == searchStr.charAt(i)) {
j++;
}
}
return j == word.length() ? true : false;
}
}
package com.anand.test;
import java.util.ArrayList;
import java.util.List;
public class LongestSubSeqSol {
public static void main(String[] args) {
List<String> dictionary = new ArrayList<>();
dictionary.add("able");
dictionary.add("ale");
dictionary.add("apple");
dictionary.add("bale");
dictionary.add("kangaroo");
String searchStr = "abppplee";
String output = getLongestSubsequence(dictionary, searchStr);
System.out.println(output);
}
private static String getLongestSubsequence(List<String> dictionary, String searchStr) {
dictionary.sort((s1, s2) -> s2.length() - s1.length());
String output = "******Not Found*****";
for (String word : dictionary) {
if (checkSubsequence(word, searchStr)) {
output = word;
break;
}
}
return output;
}
private static boolean checkSubsequence(String word, String searchStr) {
int j = 0;
for (int i = 0; i < searchStr.length(); i++) {
if (j < word.length() && word.charAt(j) == searchStr.charAt(i)) {
j++;
}
}
return j == word.length() ? true : false;
}
}
a linear time solution
---------------------------
* can we check the word from the map without scanning the whole input string (which might be order of magnitude longer) ?
* assume w is word from map, str is input.
* if we could go from the w[k] to the w[k+1] on the input string in O(1), that would fix it all.
* we can do that with pre-processing of the input string into a matrix.
* row per character in alphabet, so 256 rows.
* column per character
* pre-processing:
* for each character (c) of input string in index K, we mark it in the map @ [c,k].
* we also scan the row towards column 0 until we hit another occurrence of that character. for every column we scanned, we find the letter & point from it to the column in which c appears.
* this ensures that from a given offset, we can get the offset of any other character in O(1)
* the preprocessing time is O(256 * input string) which is linear time, although actual constant would rarely be that large.
#include <string>
#include <array>
#include <vector>
#include <unordered_set>
#include <cassert>
using namespace std;
#define NUM_MAT_ROWS 256
typedef unordered_set<string> map_t;
typedef array<size_t, NUM_MAT_ROWS> per_char_info_t;
struct input_char_next {
per_char_info_t next; // point to the next offset of character 'c' at offset 'c'.
input_char_next()
{
fill(next.begin(), next.end(), -1/*poison => no such character in higher offset*/);
}
};
typedef vector<input_char_next> input_md_t; // lookup information per character input string
class my_algorithm {
protected:
input_md_t str_lookup;
size_t n_col; // No. of matrix columns
void prepare_matrix(const string &str)
{
for (int offset = 0; offset < str.size(); ++offset) {
char ch = str[offset];
struct input_char_next &elem = str_lookup[offset];
// initialize pointing from previous characters to this one
ssize_t prev = offset;
do {
prev--;
struct input_char_next &pre = str_lookup[prev];
pre.next[ch] = offset;
} while ((prev >= 0) && (str[prev] != ch));
}
}
public:
my_algorithm()
{}
const string *
find_longest_dict_word_by_del_from_input(const string &str,
const map_t &map)
{
const string *res = nullptr;
// preprocessing
n_col = str.size();
str_lookup.resize(str.size());
prepare_matrix(str);
for (auto wit = map.begin(); wit != map.end(); ++wit) {
if (wit->size() == 0) {
continue; // not sure what to do with empty string - they can always be matched :)
}
const string &w = *wit; // this is the word we attempt to match in the input string
char first_ch = w[0];
size_t curr_offset = (first_ch == str[0]) ? 0 : str_lookup[0].next[first_ch]; // offset with which we move forward on input string as we match characters.
auto cit = w.begin();
for (++cit; (cit != w.end()) && (curr_offset != -1); ++cit) {
curr_offset = str_lookup[curr_offset].next[*cit];
}
if (curr_offset != -1) {
// the word can be made from input string - check if its longer than what we already found
if (!res || (w.size() > res->size())) {
res = &w; // we found a longer match
}
}
}
return res;
}
};
int main ()
{
my_algorithm alg;
const string *res;
{ // map is empty
const map_t map;
res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
assert(res == nullptr);
}
{ // input string is empty
const map_t map = {"eitan"};
res = alg.find_longest_dict_word_by_del_from_input("", map);
assert(res == nullptr);
}
{
const map_t map = {"ale", "apple", "monkey", "plea"};
res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
assert(*res == "apple");
}
{ // longest match isnt first & is also on end of input string
const map_t map = {"ale", "apple", "monkey", "plea"};
res = alg.find_longest_dict_word_by_del_from_input("abpcpleamonkey", map);
assert(*res == "monkey");
}
return 0;
}
import java.util.*;
public class LongSubSeq
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Enter the String: ");
String str = in.next();
int no = in.nextInt();
String dict[] = new String[no];
for(int x=0;x<no;x++)
{
dict[x] = in.nextLine();
}
String longSub = Solve(str,dict);
System.out.println(longSub);
}
public static String Solve(String str,String[] dict)
{
int len = -1;String longSub="";int dL = dict.length;
for(int x=0;x<dL;x++)
{
if(dict[x].length()>len && checkSubSeq(str,dict[x]))
{
longSub = dict[x];
len = longSub.length();
}
}
return longSub;
}
public static boolean checkSubSeq(String str,String sub)
{
StringBuffer st = new StringBuffer(str);
boolean t=true;int ind = -1;
for(int x=0;x<sub.length();x++)
{
int pos = st.indexOf(sub.charAt(x)+"");
if(pos>ind)
{
st.setCharAt(pos,' ');
ind = pos;
}
else
{
t = false;
break;
}
}
return t;
}
}
import java.util.*;
public class LongSubSeq
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Enter the String: ");
String str = in.next();
int no = in.nextInt();
String dict[] = new String[no];
for(int x=0;x<no;x++)
{
dict[x] = in.nextLine();
}
String longSub = Solve(str,dict);
System.out.println(longSub);
}
public static String Solve(String str,String[] dict)
{
int len = -1;String longSub="";int dL = dict.length;
for(int x=0;x<dL;x++)
{
if(dict[x].length()>len && checkSubSeq(str,dict[x]))
{
longSub = dict[x];
len = longSub.length();
}
}
return longSub;
}
public static boolean checkSubSeq(String str,String sub)
{
StringBuffer st = new StringBuffer(str);
boolean t=true;int ind = -1;
for(int x=0;x<sub.length();x++)
{
int pos = st.indexOf(sub.charAt(x)+"");
if(pos>ind)
{
st.setCharAt(pos,' ');
ind = pos;
}
else
{
t = false;
break;
}
}
return t;
}
}
#include <iostream>
#include <set>
using namespace std;
class SearchingLongWord {
public:
int SubSequenceChecker(string &MainWord, set<string> &WordPool);
int IsBelongToMain(string &MainWord, string &curr_word);
void set_long_WordLength(string word, int length)
{
longst_word = word;
longst_length = length;
};
int get_long_WordLength(string &word, int &length)
{
word = longst_word;
length = longst_length;
};
SearchingLongWord()
{
longst_word = "";
longst_length = 0;;
};
private:
string longst_word;
int longst_length;
};
int SearchingLongWord::IsBelongToMain(string &MainWord, string &curr_word)
{
int match_count = 0;
for(int i = 0; i < curr_word.length(); i++)
{
for(int j = 0; j < MainWord.length(); j++)
{
if(curr_word[i] == MainWord[j])
{
match_count++;
cout<<"matched "<<match_count<<endl;
}
}
}
return (match_count >= curr_word.length())?1:0;
}
int SearchingLongWord::SubSequenceChecker(string &MainWord, set<string> &WordPool)
{
for(set<string>::iterator it = WordPool.begin(); it!=WordPool.end(); it++)
{
string curr_word = *it;
if(IsBelongToMain(MainWord, curr_word))
{
int longst_length = 0;
string longst_word;
get_long_WordLength(longst_word, longst_length);
if(longst_length < curr_word.length())
{
longst_length = curr_word.length();
longst_word = curr_word;
set_long_WordLength(longst_word,longst_length);
}
}
else
cout<<"No match"<<endl;
}
if(longst_word != "")
{
cout<<longst_word<<" "<<longst_length<<endl;
return 1;
}
else
{
cout<<"No matched"<<endl;
return 0;
}
}
int main()
{
string MainWord = "abppplee";
set<string> WordPool;
WordPool.insert("able");
WordPool.insert("ale");
WordPool.insert("apple");
WordPool.insert("bale");
WordPool.insert("kangaroo");
SearchingLongWord slw;
slw.SubSequenceChecker(MainWord,WordPool);
}
#include <iostream>
#include <set>
using namespace std;
class SearchingLongWord {
public:
int SubSequenceChecker(string &MainWord, set<string> &WordPool);
int IsBelongToMain(string &MainWord, string &curr_word);
void set_long_WordLength(string word, int length)
{
longst_word = word;
longst_length = length;
};
int get_long_WordLength(string &word, int &length)
{
word = longst_word;
length = longst_length;
};
SearchingLongWord()
{
longst_word = "";
longst_length = 0;;
};
private:
string longst_word;
int longst_length;
};
int SearchingLongWord::IsBelongToMain(string &MainWord, string &curr_word)
{
int match_count = 0;
for(int i = 0; i < curr_word.length(); i++)
{
for(int j = 0; j < MainWord.length(); j++)
{
if(curr_word[i] == MainWord[j])
{
match_count++;
}
}
}
return (match_count >= curr_word.length())?1:0;
}
int SearchingLongWord::SubSequenceChecker(string &MainWord, set<string> &WordPool)
{
for(set<string>::iterator it = WordPool.begin(); it!=WordPool.end(); it++)
{
string curr_word = *it;
if(IsBelongToMain(MainWord, curr_word))
{
int longst_length = 0;
string longst_word;
get_long_WordLength(longst_word, longst_length);
if(longst_length < curr_word.length())
{
longst_length = curr_word.length();
longst_word = curr_word;
set_long_WordLength(longst_word,longst_length);
}
}
}
if(longst_word != "")
{
cout<<longst_word<<" "<<longst_length<<endl;
return 1;
}
else
{
return 0;
}
}
int main()
{
string MainWord = "abppplee";
set<string> WordPool;
WordPool.insert("able");
WordPool.insert("ale");
WordPool.insert("apple");
WordPool.insert("bale");
WordPool.insert("kangaroo");
SearchingLongWord slw;
slw.SubSequenceChecker(MainWord,WordPool);
}
public class LongestWordOFSubSequence {
public static String find(String pattern, List<String> inputList) {
String longestString = "apple";
for (String currentInput : inputList) {
if (isSubSequenceOf(pattern, currentInput))
if (isCurrentInputStringLonger(currentInput, longestString))
longestString = currentInput;
}
return longestString;
}
public static boolean isCurrentInputStringLonger(String currentInput, String longestString) {
if (currentInput.length() > longestString.length())
return true;
return false;
}
public static boolean isSubSequenceOf(String pattern, String inputString) {
char[] patternArray = pattern.toCharArray();
char[] inputStringArray = inputString.toCharArray();
int indexOfInputString = 0 ;
for (int indexOfPattern = 0; indexOfPattern < patternArray.length & indexOfInputString < inputString.length(); indexOfPattern++) {
if (patternArray[indexOfPattern] == inputStringArray[indexOfInputString])
indexOfInputString++;
}
if (indexOfInputString == inputString.length())
return true;
return false;
}
}
public class LongestWordOFSubSequence {
public static String find(String pattern, List<String> inputList) {
String longestString = "apple";
for (String currentInput : inputList) {
if (isSubSequenceOf(pattern, currentInput))
if (isCurrentInputStringLonger(currentInput, longestString))
longestString = currentInput;
}
return longestString;
}
public static boolean isCurrentInputStringLonger(String currentInput, String longestString) {
if (currentInput.length() > longestString.length())
return true;
return false;
}
public static boolean isSubSequenceOf(String pattern, String inputString) {
char[] patternArray = pattern.toCharArray();
char[] inputStringArray = inputString.toCharArray();
int indexOfInputString = 0 ;
for (int indexOfPattern = 0; indexOfPattern < patternArray.length & indexOfInputString < inputString.length(); indexOfPattern++) {
if (patternArray[indexOfPattern] == inputStringArray[indexOfInputString])
indexOfInputString++;
}
if (indexOfInputString == inputString.length())
return true;
return false;
}
}
Following is the code snippet
import java.util.List;
public class LongestWordOFSubSequence {
public static String find(String pattern, List<String> inputList) {
String longestString = "";
for (String currentInput : inputList) {
if (isSubSequenceOf(pattern, currentInput))
if (isCurrentInputStringLonger(currentInput, longestString))
longestString = currentInput;
}
return longestString;
}
public static boolean isCurrentInputStringLonger(String currentInput, String longestString) {
if (currentInput.length() > longestString.length())
return true;
return false;
}
public static boolean isSubSequenceOf(String pattern, String inputString) {
char[] patternArray = pattern.toCharArray();
char[] inputStringArray = inputString.toCharArray();
int indexOfInputString = 0 ;
for (int indexOfPattern = 0; indexOfPattern < patternArray.length & indexOfInputString < inputString.length(); indexOfPattern++) {
if (patternArray[indexOfPattern] == inputStringArray[indexOfInputString])
indexOfInputString++;
}
if (indexOfInputString == inputString.length())
return true;
return false;
}
}
Following is the test case to test above code snippet
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;
public class LongestWordOFSubSequenceTest {
@Test
public void isSubSequenceOf() throws Exception {
assertTrue(LongestWordOFSubSequence.isSubSequenceOf("abppplee","a"));
assertTrue(LongestWordOFSubSequence.isSubSequenceOf("abppplee","e"));
assertTrue(LongestWordOFSubSequence.isSubSequenceOf("abppplee","ab"));
assertTrue(LongestWordOFSubSequence.isSubSequenceOf("abppplee","abl"));
assertTrue(LongestWordOFSubSequence.isSubSequenceOf("abppplee","apple"));
assertFalse(LongestWordOFSubSequence.isSubSequenceOf("abppplee","bale"));
assertFalse(LongestWordOFSubSequence.isSubSequenceOf("abppplee","kangaroo"));
}
@Test
public void givenStringAndWordsFindLongestWordThatIsSubsequenceOfString(){
String actual = LongestWordOFSubSequence.find("abppplee", Arrays.asList("able","ale","apple","bale","kangaroo"));
assertEquals(actual,"apple");
}
@Test
public void isCurrentStringLonger() throws Exception {
assertTrue(LongestWordOFSubSequence.isCurrentInputStringLonger("John","Jon"));
assertFalse(LongestWordOFSubSequence.isCurrentInputStringLonger("Jon","John"));
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace KillTime
{
class Program
{
static void Main(string[] args)
{
List<string> data = new List<string> { "ale", "apple", "monkey", "plea" };
string S = "abpcplea";
//string S = new string("abpcplea".Reverse().ToArray());
Console.WriteLine($"{S} longest subsequent word is {LongestSubsequentWord(data, S)}");
Console.ReadLine();
}
/// <summary>
/// Return the longest subsequent <paramref name="inputString"/>'s word in <paramref name="dataset"/>
/// </summary>
/// <param name="dataset"></param>
/// <param name="inputString"></param>
/// <remarks>
/// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/// PROBLEM
/// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/// Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
/// eg:S = abpcplea, Dict = {ale, apple, monkey, plea }, the return "apple"
/// </remarks>
public static string LongestSubsequentWord(List<string> dataset, string inputString)
{
if (string.IsNullOrEmpty(inputString))
throw new ArgumentException($"bad input string");
int lastPosition, newPosition, runningLength;
string longest = "";
dataset = dataset.Distinct(StringComparer.CurrentCultureIgnoreCase).ToList().ConvertAll(x => x.ToLower());
inputString = inputString.ToLower();
for (int i = 0; i < dataset.Count; i++)
{
newPosition = runningLength = lastPosition = 0;
foreach (char ch in dataset[i])
{
newPosition = lastPosition + inputString.Substring(lastPosition).IndexOf(ch) + 1;
if (newPosition > lastPosition)
{
lastPosition = newPosition;
runningLength++;
if (dataset[i].Length == runningLength)
{
if (longest.Length < runningLength)
longest = dataset[i];
}
}
}
}
return longest;
}
}
}
It’s a DP.
Make a map of all words in dictionary as value and sorted string as key.
Have a result set of strings
Base condition if sorted string till now is in map add it to result set.
Another base condition if length of current string is equal to given string just return. This condition is after first condition.
Now traverse given string from left to right. At each point either we include it or not.
If we include call your DP function with adding current character and index moved to next.
If we don’t just increase index.
Now there may be repeating or overlapping sub problems. Cache it.
Example given a dictionary [“a”, “ab”] and string abc.
Map will be a—>a, ab —>ab
Start traverse abc
abc or bc
For abc ac or abc include b or not
For ac it will be a or ac include c or not
See the pattern. Now optimize repeat problems.
public String lookFor(String inputWord, String[] dictionary) {
Arrays.sort(dictionary);
for(int index=dictionary.length-1 ; index>0; index--) {
if(isSubsequenceOf(inputWord, dictionary[index]))
return dictionary[index];
}
return null;
}
private boolean isSubsequenceOf(String inputWord, String dictionaryWord) {
int index = 0;
int offset = 0;
for(char character : dictionaryWord.toCharArray()) {
offset = inputWord.indexOf(character, index);
if(offset >= index)
index = offset;
else
return false;
}
return true;
}
import java.util.*;
public class LongestDictWord {
public static String longestSubsequence(String[] words, String s){
HashMap<Character, ArrayList<Integer>> charIndex = hashMapString(s);
String longestSub = "";
outerloop:
for (String word : words) {
int lastIdx = 0;
for (int i = 0; i < word.length(); i++){
Character letter = word.charAt(i);
if (!charIndex.containsKey(letter)) {
break outerloop;
}
int sCharIdx = charIndex.get(letter).get(0);
if (sCharIdx >= lastIdx){
lastIdx = sCharIdx;
} else {
break outerloop;
}
}
if (word.length() > longestSub.length()) longestSub = word;
}
return longestSub;
}
public static HashMap<Character, ArrayList<Integer>> hashMapString(String s) {
HashMap<Character, ArrayList<Integer>> charIndex = new HashMap();
for (int i = 0; i < s.length(); i++){
Character c = s.charAt(i);
if (charIndex.containsKey(c)) {
charIndex.get(c).add(i);
} else {
ArrayList<Integer> idx = new ArrayList();
idx.add(i);
charIndex.put(c, idx);
}
}
return charIndex;
}
public static void main(String[] args) {
String[] words = {"able", "ale", "apple", "bale", "kangaroo"};
String s = "abppplee";
System.out.println("The is the longest subsequence of the word " + s + " is " + longestSubsequence(words, s));
}
}
package longestdictword;
import java.util.*;
/**
*
* @author amychen
*/
public class LongestDictWord {
public static String longestSubsequence(String[] words, String s){
HashMap<Character, ArrayList<Integer>> charIndex = hashMapString(s);
String longestSub = "";
outerloop:
for (String word : words) {
int lastIdx = 0;
for (int i = 0; i < word.length(); i++){
Character letter = word.charAt(i);
if (!charIndex.containsKey(letter)) {
break outerloop;
}
int sCharIdx = charIndex.get(letter).get(0);
if (sCharIdx >= lastIdx){
lastIdx = sCharIdx;
} else {
break outerloop;
}
}
if (word.length() > longestSub.length()) longestSub = word;
}
return longestSub;
}
public static HashMap<Character, ArrayList<Integer>> hashMapString(String s) {
HashMap<Character, ArrayList<Integer>> charIndex = new HashMap();
for (int i = 0; i < s.length(); i++){
Character c = s.charAt(i);
if (charIndex.containsKey(c)) {
charIndex.get(c).add(i);
} else {
ArrayList<Integer> idx = new ArrayList();
idx.add(i);
charIndex.put(c, idx);
}
}
return charIndex;
}
public static void main(String[] args) {
String[] words = {"able", "ale", "apple", "bale", "kangaroo"};
String s = "abppplee";
System.out.println("The is the longest subsequence of the word " + s + " is " + longestSubsequence(words, s));
}
}
package longestdictword;
import java.util.*;
/**
*
* @author amychen
*/
public class LongestDictWord {
public static String longestSubsequence(String[] words, String s){
HashMap<Character, ArrayList<Integer>> charIndex = hashMapString(s);
String longestSub = "";
outerloop:
for (String word : words) {
int lastIdx = 0;
for (int i = 0; i < word.length(); i++){
Character letter = word.charAt(i);
if (!charIndex.containsKey(letter)) {
break outerloop;
}
int sCharIdx = charIndex.get(letter).get(0);
if (sCharIdx >= lastIdx){
lastIdx = sCharIdx;
} else {
break outerloop;
}
}
if (word.length() > longestSub.length()) longestSub = word;
}
return longestSub;
}
public static HashMap<Character, ArrayList<Integer>> hashMapString(String s) {
HashMap<Character, ArrayList<Integer>> charIndex = new HashMap();
for (int i = 0; i < s.length(); i++){
Character c = s.charAt(i);
if (charIndex.containsKey(c)) {
charIndex.get(c).add(i);
} else {
ArrayList<Integer> idx = new ArrayList();
idx.add(i);
charIndex.put(c, idx);
}
}
return charIndex;
}
public static void main(String[] args) {
String[] words = {"able", "ale", "apple", "bale", "kangaroo"};
String s = "abppplee";
System.out.println("The is the longest subsequence of the word " + s + " is " + longestSubsequence(words, s));
}
}
def isSubSeq(string1, string2, m, n):
if m == 0: return True
if n == 0: return False
if string1[m-1] == string2[n-1]:
return isSubSeq(string1, string2, m-1, n-1)
return isSubSeq(string1, string2, m, n-1)
S = 'abpcplea'
words = list({'ale','apple','monkey','plea'})
n = len(S)
isfirst=True
lastlen=0
for i in sorted(words,reverse=True,key=len):
if isSubSeq(i, S, len(i), n):
if isfirst:
isfirst=False
lastlen=len(i)
print(i)
else:
if(lastlen==len(i)):
print(i)
Usage of Java8 so as to get the solution
import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/*Given a string S and a set of words D, find the longest word in D that is a subsequence of S.
Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters.
Note: D can appear in any format (list, hash table, prefix tree, etc.*/
public class SubSeqProblem {
//public String givenString="abppplee";
//public String[] setOfWords=new String[]{"ale","able","apple", "bale", "kangaroo"};
public String[] allSubsequence(String givenString,String[] setOfWords)
{
int numberOfwords=setOfWords.length;
String [] sequenceWords= new String[numberOfwords];
for(int i=0;i<numberOfwords;i++)
{
if (isSubsequence(givenString, setOfWords[i]))
{
sequenceWords[i]=setOfWords[i];
}
}
return sequenceWords;
}
public String longestSubSequence(String givenString,String[] setOfWords)
{
String[] sequenceString=allSubsequence(givenString, setOfWords);
Stream<String> sequenceStream= Arrays.stream(sequenceString);
String [] sequenceStr=sequenceStream.filter(x->x!=null).toArray(String[] ::new);
Optional<String> longestSeq= (Arrays.stream(sequenceStr).max(Comparator.comparingInt(String::length)));
return longestSeq.get();
}
public static boolean isSubsequence(String givenWord,String checkWord)
{
boolean isSubSeq=false;
int m=givenWord.length();
int n=checkWord.length();
int j=0;
int i=0;
for(;j<m && i<n;j++)
{
if(checkWord.charAt(i)==givenWord.charAt(j))
{
i++;
}
}
if(i==n)
{
isSubSeq=true;
}
return isSubSeq;
}
}
and
function findWord() {
var S = 'abppplee'
var D = ['able', 'ale', 'apple', 'bale', 'kangaroo']
var foundWord = ''
var maxPositions = 0
D.forEach(word => {
var countOfPositions = 0
S.split('').forEach(letter => {
var hasAPosition = word.split('').indexOf(letter) > -1
if (hasAPosition) {
countOfPositions++
}
})
if (maxPositions < countOfPositions) {
maxPositions = countOfPositions
foundWord = word
}
})
return foundWord
}
var foundWord = findWord()
console.log('most same letters in word: ', foundWord)
and
function findWord() {
var S = 'abppplee'
var D = ['able', 'ale', 'apple', 'bale', 'kangaroo']
var foundWord = ''
var maxPositions = 0
D.forEach(word => {
var countOfPositions = 0
S.split('').forEach(letter => {
var hasAPosition = word.split('').indexOf(letter) > -1
if (hasAPosition) {
countOfPositions++
}
})
if (maxPositions < countOfPositions) {
maxPositions = countOfPositions
foundWord = word
}
})
return foundWord
}
var foundWord = findWord()
console.log('most same letters in word: ', foundWord)
function findWord() {
var S = 'abppplee'
var D = ['able', 'ale', 'apple', 'bale', 'kangaroo']
var foundWord = ''
var maxPositions = 0
D.forEach(word => {
var countOfPositions = 0
S.split('').forEach(letter => {
var hasAPosition = word.split('').indexOf(letter) > -1
if (hasAPosition) {
countOfPositions++
}
})
if (maxPositions < countOfPositions) {
maxPositions = countOfPositions
foundWord = word
}
})
return foundWord
}
var foundWord = findWord()
function findWord() {
var S = 'abppplee'
var D = ['able', 'ale', 'apple', 'bale', 'kangaroo']
var foundWord = ''
var maxPositions = 0
D.forEach(word => {
var countOfPositions = 0
S.split('').forEach(letter => {
var hasAPosition = word.split('').indexOf(letter) > -1
if (hasAPosition) {
countOfPositions++
}
})
if (maxPositions < countOfPositions) {
maxPositions = countOfPositions
foundWord = word
}
})
return foundWord
}
var foundWord = findWord()
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::string;
using std::vector;
using std::map;
map<char, vector<int>> IndexByLetter(const string &word) {
map<char, vector<int>> index;
for (size_t i = 0; i < word.size(); ++i) index[word[i]].push_back(i);
return index;
}
template<typename T, typename F>
auto Memoize(T key, F function) {
static T memory_key = key;
static auto memory = function(memory_key);
if (memory_key != key) {
memory_key = key;
memory = function(memory_key);
}
return memory;
}
bool IsSubsequence(const string &mask, const string &word) {
auto index = Memoize(mask, IndexByLetter);
size_t word_remaining = word.size(), mask_remaining = mask.size();
std::vector<int> found;
while (word_remaining > 0 &&
mask_remaining >= word_remaining) { // suficient mask characters
if ((found = index[word[--word_remaining]]).empty()) return false;
mask_remaining = found.back();
found.pop_back();
}
return word_remaining == 0; // entire word match
}
string FindLargestSubsequence(const string &mask,
const vector<string> &dictionary) {
const string empty = "";
const string *largest_word = ∅
for (const string &word : dictionary)
if (word.size() > largest_word->size() && IsSubsequence(mask, word))
largest_word = &word;
return *largest_word;
}
int main(void) {
vector<string> dictionary = {"able", "ale", "apple", "bale", "kangaroo"};
string mask = "abppplee";
std::cout << "The largest word subsequence of " << mask
<< " in dictionary is " << FindLargestSubsequence(mask, dictionary)
<< std::endl;
return 0;
}
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::string;
using std::vector;
using std::map;
map<char, vector<int>> IndexByLetter(const string &word) {
map<char, vector<int>> index;
for (size_t i = 0; i < word.size(); ++i) index[word[i]].push_back(i);
return index;
}
template<typename T, typename F>
auto Memoize(T key, F function) {
static T memory_key = key;
static auto memory = function(memory_key);
if (memory_key != key) {
memory_key = key;
memory = function(memory_key);
}
return memory;
}
bool IsSubsequence(const string &mask, const string &word) {
auto index = Memoize(mask, IndexByLetter);
size_t word_remaining = word.size(), mask_remaining = mask.size();
std::vector<int> found;
while (word_remaining > 0 &&
mask_remaining >= word_remaining) { // suficient mask characters
if ((found = index[word[--word_remaining]]).empty()) return false;
mask_remaining = found.back();
found.pop_back();
}
return word_remaining == 0; // entire word match
}
string FindLargestSubsequence(const string &mask,
const vector<string> &dictionary) {
const string empty = "";
const string *largest_word = ∅
for (const string &word : dictionary)
if (word.size() > largest_word->size() && IsSubsequence(mask, word))
largest_word = &word;
return *largest_word;
}
int main(void) {
vector<string> dictionary = {"able", "ale", "apple", "bale", "kangaroo"};
string mask = "abppplee";
std::cout << "The largest word subsequence of " << mask
<< " in dictionary is " << FindLargestSubsequence(mask, dictionary)
<< std::endl;
return 0;
}
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::string;
using std::vector;
using std::map;
map<char, vector<int>> IndexByLetter(const string &word) {
map<char, vector<int>> index;
for (size_t i = 0; i < word.size(); ++i) index[word[i]].push_back(i);
return index;
}
template<typename T, typename F>
auto Memoize(T key, F function) {
static T memory_key = key;
static auto memory = function(memory_key);
if (memory_key != key) {
memory_key = key;
memory = function(memory_key);
}
return memory;
}
bool IsSubsequence(const string &mask, const string &word) {
auto index = Memoize(mask, IndexByLetter);
size_t word_remaining = word.size(), mask_remaining = mask.size();
std::vector<int> found;
while (word_remaining > 0 &&
mask_remaining >= word_remaining) { // suficient mask characters
if ((found = index[word[--word_remaining]]).empty()) return false;
mask_remaining = found.back();
found.pop_back();
}
return word_remaining == 0; // entire word match
}
string FindLargestSubsequence(const string &mask,
const vector<string> &dictionary) {
const string empty = "";
const string *largest_word = ∅
for (const string &word : dictionary)
if (word.size() > largest_word->size() && IsSubsequence(mask, word))
largest_word = &word;
return *largest_word;
}
int main(void) {
vector<string> dictionary = {"able", "ale", "apple", "bale", "kangaroo"};
string mask = "abppplee";
std::cout << "The largest word subsequence of " << mask
<< " in dictionary is " << FindLargestSubsequence(mask, dictionary)
<< std::endl;
return 0;
}
Here is the Best solution
public static List<string> WordList { get; set; }
public static string SampleWord { get; set; }
public WordCollection()
{
WordList=new List<string>(){"apple","applee","abpppee"};
SampleWord = "abppplee";
}
public string CheckResult()
{
string finalResult = "";
char[] sampleWord = SampleWord.ToCharArray();
foreach (string item in WordList)
{
string result = "";
int sampleCounter = 0;
char[] word = item.ToCharArray();
for (int i = 0; (i < word.Length )&& ((item.Length - i) <= sampleWord.Length - sampleCounter); i++)
{
if (word[i] == sampleWord[sampleCounter])
{
result += word[i];
sampleCounter++;
if (result == item && finalResult.Length<result.Length)
{
finalResult = result;
}
continue;
}
else
{
sampleCounter++;
while ((sampleWord.Length>sampleCounter) && ((item.Length-i)<=sampleWord.Length-sampleCounter))
{
if (word[i] == sampleWord[sampleCounter])
{
result += word[i];
sampleCounter++;
break;
}
sampleCounter++;
}
}
if (result == item && finalResult.Length < result.Length)
{
finalResult = result;
}
}
}
return finalResult;
}
public static List<string> WordList { get; set; }
public static string SampleWord { get; set; }
public WordCollection()
{
WordList=new List<string>(){"apple","applee","abpppee"};
SampleWord = "abppplee";
}
public string CheckResult()
{
string finalResult = "";
char[] sampleWord = SampleWord.ToCharArray();
foreach (string item in WordList)
{
string result = "";
int sampleCounter = 0;
char[] word = item.ToCharArray();
for (int i = 0; (i < word.Length )&& ((item.Length - i) <= sampleWord.Length - sampleCounter); i++)
{
if (word[i] == sampleWord[sampleCounter])
{
result += word[i];
sampleCounter++;
if (result == item && finalResult.Length<result.Length)
{
finalResult = result;
}
continue;
}
else
{
sampleCounter++;
while ((sampleWord.Length>sampleCounter) && ((item.Length-i)<=sampleWord.Length-sampleCounter))
{
if (word[i] == sampleWord[sampleCounter])
{
result += word[i];
sampleCounter++;
break;
}
sampleCounter++;
}
}
if (result == item && finalResult.Length < result.Length)
{
finalResult = result;
}
}
}
return finalResult;
}
package com.google.practice;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class LongestWordInString {
List<String> findLongestWordInString(List<String> dict, String input){
Map<String, List<Integer>> map = new HashMap<String,List<Integer>>();
List<Integer> integerList;
for(int i = 0; i < input.length(); i++){
if(map.containsKey(Character.toString(input.charAt(i)))){
integerList = map.get(Character.toString(input.charAt(i)));
integerList.add(new Integer(i));
map.put(Character.toString(input.charAt(i)),integerList);
}
else{
integerList = new ArrayList<Integer>();
integerList.add(i);
map.put(Character.toString(input.charAt(i)),integerList);
}
}
Set<Entry<String, List<Integer>>> set = map.entrySet();
Iterator<Entry<String, List<Integer>>> itr = set.iterator();
while(itr.hasNext()){
Entry<String,List<Integer>> entrySet = (Entry<String, List<Integer>>) itr.next();
integerList = entrySet.getValue();
integerList.add(integerList.size());
map.put(entrySet.getKey(),integerList);
}
String finalString = null;
boolean isLongestString = false;
int index = 0;
List<String> longestStringList = new ArrayList<String>();
for(String dictWord : dict){
finalString = compareString(dictWord,input,map);
if(finalString.equals(dictWord)){
finalString = dictWord;
if(longestStringList.size() == 0){
longestStringList.add(index,dictWord);
}
else if(finalString.length() > longestStringList.get(0).length()){
isLongestString = true;
}
}
if(finalString.length() >= longestStringList.get(0).length() && !finalString.equals(longestStringList.get(0))){
if(isLongestString){
longestStringList.remove(0);
isLongestString = false;
}
longestStringList.add(finalString);
index++;
}
}
return longestStringList;
}
String compareString(String dictWord,String input,Map<String, List<Integer>> map){
int tmpLength = 0;
int tempCount = 0;
String sb = new String();
int inputLength = input.length();
int prevIndex = 0;
while(inputLength != 0){
if(tmpLength < dictWord.length()){
if(map.containsKey(Character.toString(dictWord.charAt(tempCount)))){
ArrayList<Integer> indexList = (ArrayList<Integer>) map.get(Character.toString(dictWord.charAt(tempCount)));
int index = indexList.size();
if(input.isEmpty() || prevIndex <= input.lastIndexOf(Character.toString(dictWord.charAt(tempCount))))
{
prevIndex =input.indexOf(Character.toString(dictWord.charAt(tempCount)));
if(!sb.contains(Character.toString(dictWord.charAt(tempCount)))){
sb = sb.concat(Character.toString(dictWord.charAt(tempCount)));
indexList.set(index-1, indexList.get(index-1)-1);
tempCount++;
tmpLength++;
}
else{
if((indexList.get(index-1) > 0)){
sb = sb.concat(Character.toString(dictWord.charAt(tempCount)));
indexList.set(index-1, indexList.get(index-1)-1);
tempCount++;
tmpLength++;
}
}
}
}
}
inputLength--;
}
return sb;
}
public static void main(String[] args) {
List<String> dict = new ArrayList<String>(){private static final long serialVersionUID = 1L;};
dict.add("able");
dict.add("ale");
dict.add("appple");
dict.add("bale");
dict.add("kangaroo");
String input = "abpplee";
LongestWordInString lws = new LongestWordInString();
List<String> words = lws.findLongestWordInString(dict, input);
for(String word:words){
System.out.println(word);
}
}
}
var S = 'abppplee';
var D = ["able", "ale", "apple", "bale", "kangaroo"];
const challenge = (S,D) => {
let ans = {word:null, length:0};
let map = new Map();
for (let i = 0; i < S.length ; i ++)
map.set(S[i], map.get(S[i]) + 1 || 1)
for (let j = 0; j < D.length ; j++){
let length = 0;
for (let k = 0; k < D[j].length ; k++){
if (map.has(D[j][k])) length++;
}
if (length > ans.length) ans = {word:D[j], length};
}
return ans;
}
console.log(challenge(S,D));
feedback for my JavaScript solution please!
var S = 'abppplee';
var D = ["able", "ale", "apple", "bale", "kangaroo"];
const challenge = (S,D) => {
let ans = {word:null, length:0};
let map = new Map();
for (let i = 0; i < S.length ; i ++)
map.set(S[i], map.get(S[i]) + 1 || 1)
for (let j = 0; j < D.length ; j++){
let length = 0;
for (let k = 0; k < D[j].length ; k++){
if (map.has(D[j][k])) length++;
}
if (length > ans.length) ans = {word:D[j], length};
}
return ans;
}
console.log(challenge(S,D));
Feedback for my JavaScript solution please!
In Node.js :
function getIfSusbstrcanbeformed(str, subs){
let count =0;
for (let i = 0, j = 0; i < str.length && j<subs.length;) { // n
if(str.charAt(i)===subs.charAt(j)){ //n
i++;
j++;
count++;
if(count===subs.length) //n
return 1;
} else{
i++;
}
}
return 0;
}
let word = "cabaleapple";
let subArr=["able", "caleapple", "apple", "balele", "kangaroo"];
subArr = subArr.sort((a, b) => b.length - a.length);
console.log('subs',subArr);
let greatest="";
subArr.some((curStr)=>{
if(getIfSusbstrcanbeformed(word,curStr)===1){
greatest = curStr;
return true;
}
});
console.log('the longest word is : ',greatest);
Just started programming in Java. Please comment if correction needed. Hope you like it.
public class theLongestWord {
public static void main(String args[]){
String s="abppplee";
String[] d={"able", "ale", "apple", "bale", "kangaroo","abpple"};
String longestWordString=longestWord(s,d);
}
private static String longestWord(String s,String[] d){
String lastWord="";
int charPos;
for(String w:d){
charPos=0;
if(lastWord.length()<w.length()) {
for (int i = 0; i < s.length(); i++) {
if (w.charAt(charPos) == s.charAt(i)) {
charPos++;
}
if (charPos == w.length()) {
if (lastWord.length() < w.length()) {
lastWord = w;
}
break;
}
}
}
}
return lastWord;
}
}
public String findLongestWordInString(String str, List<String> words) {
Collections.sort(words, new Comp());
char[] chArr = str.toCharArray();
HashMap<Character, List<Integer>> charToIndexeMap = new HashMap();
for (int i = 0; i < chArr.length; i++) {
char c = chArr[i];
if (charToIndexeMap.containsKey(c)) {
charToIndexeMap.get(c).add(i);
} else {
ArrayList<Integer> indexes = new ArrayList<>();
indexes.add(i);
charToIndexeMap.put(c, indexes);
}
}
for (String word : words) {
int pos = 0;
for (Character c : word.toCharArray()) {
List<Integer> possiblePosition = new ArrayList<>();
if (!charToIndexeMap.containsKey(c))
break;
for (Integer p : charToIndexeMap.get(c)) {
if (p >= pos)
possiblePosition = charToIndexeMap.get(c);
}
if (possiblePosition.size() == 0)
break;
pos = possiblePosition.get(0) + 1;
return word;
}
}
return null;
}
public String findLongestWordInString(String str, List<String> words) {
Collections.sort(words, new Comp());
char[] chArr = str.toCharArray();
HashMap<Character, List<Integer>> charToIndexeMap = new HashMap();
for (int i = 0; i < chArr.length; i++) {
char c = chArr[i];
if (charToIndexeMap.containsKey(c)) {
charToIndexeMap.get(c).add(i);
} else {
ArrayList<Integer> indexes = new ArrayList<>();
indexes.add(i);
charToIndexeMap.put(c, indexes);
}
}
for (String word : words) {
int pos = 0;
for (Character c : word.toCharArray()) {
List<Integer> possiblePosition = new ArrayList<>();
if (!charToIndexeMap.containsKey(c))
break;
for (Integer p : charToIndexeMap.get(c)) {
if (p >= pos)
possiblePosition = charToIndexeMap.get(c);
}
if (possiblePosition.size() == 0)
break;
pos = possiblePosition.get(0) + 1;
return word;
}
}
return null;
}
public String findLongestWordInString(String str, List<String> words) { Collections.sort(words, new Comp()); char[] chArr = str.toCharArray(); HashMap<Character, List<Integer>> charToIndexeMap = new HashMap(); for (int i = 0; i < chArr.length; i++) { char c = chArr[i]; if (charToIndexeMap.containsKey(c)) { charToIndexeMap.get(c).add(i); } else { ArrayList<Integer> indexes = new ArrayList<>(); indexes.add(i); charToIndexeMap.put(c, indexes); } } for (String word : words) { int pos = 0; for (Character c : word.toCharArray()) { List<Integer> possiblePosition = new ArrayList<>(); if (!charToIndexeMap.containsKey(c)) break; for (Integer p : charToIndexeMap.get(c)) { if (p >= pos) possiblePosition = charToIndexeMap.get(c); } if (possiblePosition.size() == 0) break; pos = possiblePosition.get(0) + 1; return word; } } return null;
}
If anyone wants a different approach in Python, here's mine:
S = "abppplee" #mother string
D = {"able", "ale", "apple", "bale", "kangaroo"} #set of words
def get_longest_word_in_string(S, D):
possible_solutions = []
for word in D:
correct = False
position = 0
for letter in word:
for x in range(position, len(S)):
if letter == S[x]:
position+=1
break
if position == len(word):
correct = True
if correct:
possible_solutions.append(word)
return possible_solutions
if __name__ == '__main__':
possible_solutions = get_longest_word_in_string(S, D)
print(max(possible_solutions, key=len))
If anyone wants a different approach in Python, here's mine:
S = "abppplee" #mother string
D = {"able", "ale", "apple", "bale", "kangaroo"} #set of words
def get_longest_word_in_string(S, D):
possible_solutions = []
for word in D:
correct = False
position = 0
for letter in word:
for x in range(position, len(S)):
if letter == S[x]:
position+=1
break
if position == len(word):
correct = True
if correct:
possible_solutions.append(word)
return possible_solutions
if __name__ == '__main__':
possible_solutions = get_longest_word_in_string(S, D)
print(max(possible_solutions, key=len))
If anyone wants a different approach in Python, here's mine:
S = "abppplee" #mother string
D = {"able", "ale", "apple", "bale", "kangaroo"} #set of words
def get_longest_word_in_string(S, D):
possible_solutions = []
for word in D:
correct = False
position = 0
for letter in word:
for x in range(position, len(S)):
if letter == S[x]:
position+=1
break
if position == len(word):
correct = True
if correct:
possible_solutions.append(word)
return possible_solutions
if __name__ == '__main__':
possible_solutions = get_longest_word_in_string(S, D)
print(max(possible_solutions, key=len))
If anyone wants a different approach in Python, here's mine:
S = "abppplee" #mother string
D = {"able", "ale", "apple", "bale", "kangaroo"} #set of words
def get_longest_word_in_string(S, D):
possible_solutions = []
for word in D:
correct = False
position = 0
for letter in word:
for x in range(position, len(S)):
if letter == S[x]:
position+=1
break
if position == len(word):
correct = True
if correct:
possible_solutions.append(word)
return possible_solutions
if __name__ == '__main__':
possible_solutions = get_longest_word_in_string(S, D)
print(max(possible_solutions, key=len))
public class DictSub {
public static void main(String[] args) {
String[] dict = {"abled", "ale", "apples", "bale", "kangaroo"};
String input = "abppplee";
String longestWord = "";
for (String word : dict) {
if (word.length() < longestWord.length()) {
continue;
}
if (word.length() > input.length()) {
continue;
}
int wordIndex = 0;
int inputIndex = 0;
while (inputIndex < input.length() && wordIndex < word.length()) {
if (word.charAt(wordIndex) == input.charAt(inputIndex)) {
wordIndex++;
}
inputIndex++;
}
if (wordIndex >= word.length()) {
longestWord = word;
}
}
System.out.println("Longest Word: " + longestWord);
}
}
public class DictSub {
public static void main(String[] args) {
String[] dict = {"abled", "ale", "apples", "bale", "kangaroo"};
String input = "abppplee";
String longestWord = "";
for (String word : dict) {
if (word.length() < longestWord.length()) {
continue;
}
if (word.length() > input.length()) {
continue;
}
int wordIndex = 0;
int inputIndex = 0;
while (inputIndex < input.length() && wordIndex < word.length()) {
if (word.charAt(wordIndex) == input.charAt(inputIndex)) {
wordIndex++;
}
inputIndex++;
}
if (wordIndex >= word.length()) {
longestWord = word;
}
}
System.out.println("Longest Word: " + longestWord);
}
}
function cryptogram(str, arr) {
let lgToSm = arr.sort((a, b) => b.length - a.length);
let answer = "";
lgToSm.filter(el => {
if (answer) return answer;
for (let i = 0; i < el.length; i++) {
if (el.indexOf(el[i]) <= str.indexOf(el.charAt(i))) {
answer += el[i];
} else break;
}
});
return answer;
}
console.log(
cryptogram("abpplee", ["able", "ale", "apple", "bale", "kangaroo"])
);
Making the Question Simpler 🤑
We are given two things..
A string, 'abppplee'..
.. and an array of words, ['apple', 'able', 'ale', 'bale', 'kangaroo'].
We're searching for what we'll call a cryptogram.
A cryptogram is a word hiding in a larger word.
The letters composing the hidden word may be separated by any number of other characters.
For example, looking at 'abpplee' we can detect the word 'apple'..
A b P P L E e
We may not rearrange letters, yet will detect the correct characters sequentially.
Note, the word BALE exists in our string, yet requires rearrangement, so thusly is illegal.
Our final objective is to return the longest hidden word from our array.
#include<QDebug>
#include<QVector>
class Entry{
public:
Entry(){matchIndex = 0 ;}
Entry(QString content){
this->content = content;
matchIndex = 0 ;
}
void feed(QChar c ){
if(matchIndex == content.length()){
return ;
}
if(content.at(matchIndex) == c){
matchIndex ++ ;
}
}
bool isFindAllChar()const {
return matchIndex == content.length();
}
QString getContent()const{
return content;
}
private:
QString content;
int matchIndex;
};
bool entryLengthGreaterThan(const Entry &s1, const Entry &s2)
{
return s1.getContent().length() > s2.getContent().length();
}
int main(int , char *[])
{
QString dictionary[] = {"able", "ale", "apple", "bale", "kangaroo"};
QString content = "abppplee";
QVector<Entry> entrys;
for(QString word : dictionary){
entrys.append(Entry(word));
}
for(QChar c : content){
for(Entry &entry : entrys){
entry.feed(c);
}
}
qSort(entrys.begin(),entrys.end(),entryLengthGreaterThan);
for(Entry entry : entrys){
if(entry.isFindAllChar()){
qDebug()<< entry.getContent();
break;
}
}
return 0;
}
My solution in Golang =)
package main
import (
"fmt"
)
func main() {
base := "abppplee"
words := []string{"able", "ale", "apple", "bale", "kangaroo"}
rightOrderWords := findRightOrderWords(words, base)
posOfLongest := findPosOfLongest(rightOrderWords)
if posOfLongest > -1 {
fmt.Println("word found:", rightOrderWords[posOfLongest])
} else {
fmt.Println("word not found")
}
}
func findPosOfLongest(words []string) int {
maxLength := 0
posOfLongest := -1
for pos, word := range words {
length := len(word)
if length > maxLength {
maxLength = length
posOfLongest = pos
}
}
return posOfLongest
}
func findRightOrderWords(words []string, base string) []string {
rightOrderWords := []string{}
for _, word := range words {
if isRightOrder(word, base) {
rightOrderWords = append(rightOrderWords, word)
}
}
return rightOrderWords
}
func isRightOrder(word, base string) bool {
type Carcase struct {
Chars map[string]int
}
asCarcase := func(str string) Carcase {
c := Carcase{
Chars: make(map[string]int),
}
for i, char := range str {
c.Chars[string(char)] = i
}
return c
}
carcase := asCarcase(base)
rightOrder := true
for pos, char := range word {
charStr := string(char)
if pos == 0 {
if carcase.Chars[charStr] != 0 {
rightOrder = false
break
}
} else if pos > 0 {
charOrder, ok := carcase.Chars[charStr]
if !ok {
rightOrder = false
break
}
prevPos := pos - 1
prevChar := string(word[prevPos])
prevCharOrder, ok := carcase.Chars[prevChar]
if !ok {
rightOrder = false
break
}
if prevCharOrder > charOrder {
rightOrder = false
break
}
}
}
return rightOrder
}
My solution in Golang =)
package main
import (
"fmt"
)
func main() {
base := "abppplee"
words := []string{"able", "ale", "apple", "bale", "kangaroo"}
rightOrderWords := findRightOrderWords(words, base)
posOfLongest := findPosOfLongest(rightOrderWords)
if posOfLongest > -1 {
fmt.Println("word found:", rightOrderWords[posOfLongest])
} else {
fmt.Println("word not found")
}
}
func findPosOfLongest(words []string) int {
maxLength := 0
posOfLongest := -1
for pos, word := range words {
length := len(word)
if length > maxLength {
maxLength = length
posOfLongest = pos
}
}
return posOfLongest
}
func findRightOrderWords(words []string, base string) []string {
rightOrderWords := []string{}
for _, word := range words {
if isRightOrder(word, base) {
rightOrderWords = append(rightOrderWords, word)
}
}
return rightOrderWords
}
func isRightOrder(word, base string) bool {
type Carcase struct {
Chars map[string]int
}
asCarcase := func(str string) Carcase {
c := Carcase{
Chars: make(map[string]int),
}
for i, char := range str {
c.Chars[string(char)] = i
}
return c
}
carcase := asCarcase(base)
rightOrder := true
for pos, char := range word {
charStr := string(char)
if pos == 0 {
if carcase.Chars[charStr] != 0 {
rightOrder = false
break
}
} else if pos > 0 {
charOrder, ok := carcase.Chars[charStr]
if !ok {
rightOrder = false
break
}
prevPos := pos - 1
prevChar := string(word[prevPos])
prevCharOrder, ok := carcase.Chars[prevChar]
if !ok {
rightOrder = false
break
}
if prevCharOrder > charOrder {
rightOrder = false
break
}
}
}
return rightOrder
}
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
string[] d = new string[] { "able", "ale", "apple", "bale", "kangaroo" };
string s = "abppplee";
bool letterFound = false;
int letterFoundCounter = 0;
int resultCounter = 0;
string longestWord = string.Empty;
var baseLetters = s.ToArray();
for(int iWord = 0; iWord < d.Length; iWord++)
{
if(d[iWord].Length > longestWord.Length)
{
string tempWord = d[iWord];
var letters = d[iWord].ToArray();
for (int iArrWord = 0; iArrWord < letters.Length; iArrWord++)
{
char letter = letters[iArrWord];
while (!letterFound && letterFoundCounter < baseLetters.Length)
{
if (letter == baseLetters[letterFoundCounter])
{
letterFound = true;
letterFoundCounter++;
resultCounter++;
}
else
{
letterFoundCounter++;
}
}
letterFound = false;
}
if (letters.Length == resultCounter)
{
Console.WriteLine($"{d[iWord]} is a subsequence of {s}");
if (iWord == 0) longestWord = d[iWord];
if (d[iWord].Length > longestWord.Length) longestWord = d[iWord];
}
letterFoundCounter = 0;
resultCounter = 0;
}
}
Console.WriteLine($"{longestWord} is the longest subsequence word of {s}");
public class Main {
public static void main(String[] args) {
final String S = "abppplee";
final ArrayList<String> dictionary=new ArrayList<>(Arrays.asList("able", "ale", "apple", "bale", "kangaroo"));
System.out.println("Solution is:"+findLongestSubsequenceWord(S,dictionary));
}
//my implementation of what is described as 'greedy algorithm' in the solutions commentary
//For each word in d, take the first charakter and then search this character in s
//Each time a matching character is found, compare the second character of word w with the character at position found+1 and so on
private static String findLongestSubsequenceWord(final String s, final ArrayList<String> d){
//at the beginning, sort the dictionary by its word's length in descending order
//This way we know we have found the optimal match once we have found the first match
Collections.sort(d,(s1,s2)->(Integer.compare(s2.length(),s1.length())));
//
//if(s.length()==0 || d.size()==0)return null;
for(final String word:d) {
System.out.println("Processing:"+word);
int matchCounter=0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == word.charAt(matchCounter)) {
//we have found the first matching character
//look if all the remaining characters of the word are inside s (in the right order)
matchCounter++;
if(matchCounter==word.length()-1){
System.out.println(word);
return word;
}
}
}
}
return null;
}
}
I've seen a lot of possible solutions building the query on your own, but do we really need to reinvent the wheel in this case? The problem never mentioned the desired complexity or how critical is the processing speed for this problem, so for a first version I'd simply give a shot using a simple regex like this, where anyone could quickly understand and spot what's going on:
public String getLongestWord(String S, List<String> D) {
String result = "";
for (String W : D) {
if (hasGreaterLength(W, result) && isSubsequence(S, W)) {
result = W;
}
}
return result;
}
protected boolean hasGreaterLength(String a, String b) {
return a.length() > b.length();
}
protected boolean isSubsequence(String S, String W) {
char[] wChars = W.toCharArray();
StringBuilder regex = new StringBuilder();
for (char c : wChars) {
regex.append(".*");
regex.append("[" + c + "]");
}
regex.append(".*");
return S.matches(regex.toString());
}
public string LongSubsSeq(string[] d, string s)
{
if (s.Length <= 0)
return string.Empty;
int max = 0;
string r = string.Empty;
foreach (var w in d)
{
int i = 0;
int j = 0;
int p = 0;
StringBuilder sb = new StringBuilder();
while (w.Length >= 1 && i < w.Length)
{
if (s[j] == w[i])
{
sb.Append(w[i]);
i++;
j++;
p = j;
}
else
{
j++;
}
if (j >= s.Length)
{
break;
}
}
if(sb.ToString().Equals(w))
{
if(max <= w.Length)
{
r = sb.ToString();
max = Math.Max(max, w.Length);
r = w;
}
}
}
return r;
}
This is my solution for JavaScript, May not be the best but probably easy to read? Let me know your thoughts.
function findTheWord(S, D){
/// Sort the words
D.sort((a, b) => b.length - a.length)
/// Loop on the words until they have been all looped on
loop1:
while (D.length != 0) {
var word = D.shift()
var incrementPosition = 0;
for (var i = 0; i < word.split('').length; i++) {
/// Check if there is a preceding match
var foundIndex = S.indexOf(word[i], incrementPosition);
/// If no match then continue to the next word
if (foundIndex === -1){
continue loop1;
}
else
incrementPosition = foundIndex;
}
return word
}
}
findTheWord("abppplee", ["able", "ale", "apple", "bale", "kangaroo"]) /// apple
findTheWord("abppplee", ["able", "aleeeeeeee", "apple", "bale", "kangaroo"]) /// aleeeeeeee
findTheWord("abpeepplee", ["able", "abbeeleeeee", "apple", "bale", "kangaroo"]) /// abbeeleeeee
JavaScript using RegExp:
const S = "abppplee";
const D = ["able", "ale", "apple", "bale", "kangaroo"];
D.sort((a, b) => {
return b.length - a.length;
});
const dRegex = D.map((W) => new RegExp(W.replace(/(.)/g, "$1.*")));
function findLongestSubstr(){
for (let i = 0; i < D.length; i++){
if (dRegex[i].test(S)){
return D[i];
}
}
return null;
}
console.log(findLongestSubstr()); //apple
Here's my solution in golang
package main
import (
"fmt"
)
func main() {
var S = "abppplee"
var words = []string{"able", "ale", "apple", "bale", "kangaroo"}
isSubSequence := func(word, sequence string) (int, bool) {
j := 0
for i := 0; i < len(sequence) && j < len(word); i++ {
if sequence[i] == word[j] {
j++
}
}
if j == len(word) {
return j, true
}
return -1, false
}
var max, idx int
for i, w := range words {
n, ok := isSubSequence(w, S)
if ok && max < n {
max = n
idx = i
}
}
fmt.Printf("The longest subsequence is %s\n", words[idx])
}
There is a much much much simpler approach.
Observe the algorithm - ( ZoomBA : which works my the way ) :
def find_max_len( words, S ){
max_len = 0
result = ''
for ( w : words ){
// list contains comparision
if ( w.value <= S.value && size(w) > max_len ){
result = w ; max_len = size(w)
}
}
return result
}
S = 'abpcplea'
words = set( 'ale', 'apple', 'monkey', 'plea' )
println ( find_max_len(words,S) )
The only problem is how do you implement this <= operator?
That is simple, by simply implementing an mset comparison.
Convert an array of elements into multi-set where it is actually a dictionary of key-element against the value - no of items in the collection.
The following is the code if you choose to do the Trie approach
import java.io.*;
import java.util.*;
public class LongestStringDictionary {
public static void main(String[] args) {
Trie t = new Trie();
t.add("apple");
t.add("ale");
t.add("monkey");
t.add("plea");
System.out.println(t.findLongestString("abpcplea"));
}
public static class Trie {
Node root;
public Trie() {
this.root = new Node();
}
public void add(String s) {
Node current = root;
for(int i = 0; i < s.length(); i++) {
add(current, s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
public void add(Node root, char c) {
if(root == null) return;
if(!root.children.containsKey(c)) root.children.put(c, new Node());
}
public String findLongestString(String s) {
String currentLongest = "";
int index = 0;
while(index+currentLongest.length() < s.length()) {
Node current = root;
StringBuilder sb = new StringBuilder();
for(int i = index; i < s.length(); i++) {
if(current.children.containsKey(s.charAt(i))) {
sb.append(s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
if(sb.length() > currentLongest.length()) {
currentLongest = sb.toString();
}
index++;
}
return currentLongest;
}
}
public static class Node {
HashMap<Character, Node> children;
public Node() {
this.children = new HashMap<>();
}
}
}
The following is the code if you so choose to do the Trie approach
import java.io.*;
import java.util.*;
public class LongestStringDictionary {
public static void main(String[] args) {
Trie t = new Trie();
t.add("apple");
t.add("ale");
t.add("monkey");
t.add("plea");
System.out.println(t.findLongestString("abpcplea"));
}
public static class Trie {
Node root;
public Trie() {
this.root = new Node();
}
public void add(String s) {
Node current = root;
for(int i = 0; i < s.length(); i++) {
add(current, s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
public void add(Node root, char c) {
if(root == null) return;
if(!root.children.containsKey(c)) root.children.put(c, new Node());
}
public String findLongestString(String s) {
String currentLongest = "";
int index = 0;
while(index+currentLongest.length() < s.length()) {
Node current = root;
StringBuilder sb = new StringBuilder();
for(int i = index; i < s.length(); i++) {
if(current.children.containsKey(s.charAt(i))) {
sb.append(s.charAt(i));
current = current.children.get(s.charAt(i));
}
}
if(sb.length() > currentLongest.length()) {
currentLongest = sb.toString();
}
index++;
}
return currentLongest;
}
}
public static class Node {
HashMap<Character, Node> children;
public Node() {
this.children = new HashMap<>();
}
}
}
- Sandy0109 January 29, 2017package careerCup; import java.util.ArrayList; import java.util.List; /** * <p> * Giving a string and an string dictionary, find the longest string in * dictionary which can formed by deleting some characters of the giving string. * eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple" * </p> * * @author * */ //Added few conditions to check if there are multiple longest string with same length. public class LongestStringAfterCharacterDelete { List findLongestString(List<String> dict, String input) { String finalString = null; List<String> multipleLongestString = new ArrayList<String>(); int index = 0; boolean isLongStringFound = false; for (String tempDict : dict) { finalString = compareString(tempDict, input); if (tempDict.equals(finalString)) { finalString = tempDict; if (multipleLongestString.size() == 0) { multipleLongestString.add(index, finalString); } else if (finalString.length() > multipleLongestString.get(0) .length()) { isLongStringFound = true; } } if (finalString.length() >= multipleLongestString.get(0).length() && !finalString.equals(multipleLongestString.get(0))) { if (isLongStringFound) { multipleLongestString.remove(0); isLongStringFound = false; } multipleLongestString.add(0, finalString); index++; } } printList(multipleLongestString); return multipleLongestString; } void printList(List<String> inputList) { for (String longestString : inputList) { System.out.println(longestString); } } String compareString(String tempDict, String input) { StringBuffer sb = new StringBuffer(); int tempCount = 0; int inputStringLength = input.length(); int dictLength = 0; while (inputStringLength != 0) { if (dictLength < tempDict.length()) { if (input.toLowerCase().contains( Character.toString(tempDict.toLowerCase().charAt( tempCount)))) { sb.append(tempDict.charAt(tempCount)); tempCount++; dictLength++; } } inputStringLength--; } return sb.toString(); } public static void main(String[] args) { List<String> dict = new ArrayList<String>(); dict.add("ale"); dict.add("applee"); dict.add("monkey"); dict.add("plea"); String input = "abpcpleeaDChsssgtrsssmonkey"; LongestStringAfterCharacterDelete ls = new LongestStringAfterCharacterDelete(); ls.findLongestString(dict, input); } }