Dando un diccionario y una string ‘str’, encuentre la string más larga en el diccionario que se puede formar eliminando algunos caracteres de la ‘str’ dada.
Ejemplos:
C++
// C++ program to find largest word in Dictionary
// by deleting some characters of given string
#include <bits/stdc++.h>
using namespace std;
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
bool isSubSequence(string str1, string str2)
{
int m = str1.length(), n = str2.length();
int j = 0; // For index of str1 (or subsequence
// Traverse str2 and str1, and compare current
// character of str2 with first unmatched char
// of str1, if matched then move ahead in str1
for (int i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
// If all characters of str1 were found in str2
return (j == m);
}
// Returns the longest string in dictionary which is a
// subsequence of str.
string findLongestString(vector<string> dict, string str)
{
string result = "";
int length = 0;
// Traverse through all words of dictionary
for (string word : dict) {
// If current word is subsequence of str and is
// largest such word so far.
if (length < word.length()
&& isSubSequence(word, str)) {
result = word;
length = word.length();
}
}
// Return longest string
return result;
}
// Driver program to test above function
int main()
{
vector<string> dict
= { "ale", "apple", "monkey", "plea" };
string str = "abpcplea";
cout << findLongestString(dict, str) << endl;
return 0;
}
Java
// Java program to find largest
// word in Dictionary by deleting
// some characters of given String
import java.util.*;
class GFG
{
// Returns true if str1[] is a
// subsequence of str2[]. m is
// length of str1 and n is length of str2
static boolean isSubSequence(String str1,
String str2)
{
int m = str1.length(), n = str2.length();
int j = 0; // For index of str1 (or subsequence)
// Traverse str2 and str1, and compare current
// character of str2 with first unmatched char
// of str1, if matched then move ahead in str1
for (int i = 0; i < n && j < m; i++)
{
if (str1.charAt(j) == str2.charAt(i))
{
j++;
}
}
// If all characters of str1
// were found in str2
return (j == m);
}
// Returns the longest String
// in dictionary which is a
// subsequence of str.
static String findLongestString(Vector<String> dict,
String str)
{
String result = "";
int length = 0;
// Traverse through all words of dictionary
for (String word : dict)
{
// If current word is subsequence of str
// and is largest such word so far.
if (length < word.length() &&
isSubSequence(word, str))
{
result = word;
length = word.length();
}
}
// Return longest String
return result;
}
// Driver code
public static void main(String[] args)
{
String[] arr = {"ale", "apple", "monkey", "plea"};
Vector dict = new Vector(Arrays.asList(arr));
String str = "abpcplea";
System.out.println(findLongestString(dict, str));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find largest word in Dictionary # by deleting some characters of given string # Returns true if str1[] is a subsequence of str2[]. # m is length of str1 and n is length of str2 def isSubSequence(str1, str2): m = len(str1); n = len(str2); j = 0; # For index of str1 (or subsequence # Traverse str2 and str1, and compare current # character of str2 with first unmatched char # of str1, if matched then move ahead in str1 i = 0; while (i < n and j < m): if (str1[j] == str2[i]): j += 1; i += 1; # If all characters of str1 were found in str2 return (j == m); # Returns the longest string in dictionary which is a # subsequence of str. def findLongestString(dict1, str1): result = ""; length = 0; # Traverse through all words of dictionary for word in dict1: # If current word is subsequence of str and is largest # such word so far. if (length < len(word) and isSubSequence(word, str1)): result = word; length = len(word); # Return longest string return result; # Driver program to test above function dict1 = ["ale", "apple", "monkey", "plea"]; str1 = "abpcplea" ; print(findLongestString(dict1, str1)); # This code is conribued by mits
C#
// C# program to find largest
// word in Dictionary by deleting
// some characters of given String
using System;
using System.Collections.Generic;
class GFG
{
// Returns true if str1[] is a
// subsequence of str2[]. m is
// length of str1 and n is length of str2
static bool isSubSequence(String str1,
String str2)
{
int m = str1.Length, n = str2.Length;
int j = 0; // For index of str1 (or subsequence)
// Traverse str2 and str1, and compare current
// character of str2 with first unmatched char
// of str1, if matched then move ahead in str1
for (int i = 0; i < n && j < m; i++)
{
if (str1[j] == str2[i])
{
j++;
}
}
// If all characters of str1
// were found in str2
return (j == m);
}
// Returns the longest String
// in dictionary which is a
// subsequence of str.
static String findLongestString(List<String> dict,
String str)
{
String result = "";
int length = 0;
// Traverse through all words of dictionary
foreach (String word in dict)
{
// If current word is subsequence of str
// and is largest such word so far.
if (length < word.Length &&
isSubSequence(word, str))
{
result = word;
length = word.Length;
}
}
// Return longest String
return result;
}
// Driver code
public static void Main(String[] args)
{
String[] arr = {"ale", "apple", "monkey", "plea"};
List<String> dict = new List<String>(arr);
String str = "abpcplea";
Console.WriteLine(findLongestString(dict, str));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP program to find largest word in Dictionary
// by deleting some characters of given string
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
function isSubSequence($str1, $str2)
{
$m = strlen($str1);
$n = strlen($str2);
$j = 0; // For index of str1 (or subsequence
// Traverse str2 and str1, and compare current
// character of str2 with first unmatched char
// of str1, if matched then move ahead in str1
for ($i = 0; $i < $n && $j < $m; $i++)
if ($str1[$j] == $str2[$i])
$j++;
// If all characters of str1 were found in str2
return ($j == $m);
}
// Returns the longest string in dictionary which is a
// subsequence of str.
function findLongestString($dict, $str)
{
$result = "";
$length = 0;
// Traverse through all words of dictionary
foreach ($dict as $word)
{
// If current word is subsequence
// of str and is largest
// such word so far.
if ($length < strlen($word) &&
isSubSequence($word, $str))
{
$result = $word;
$length = strlen($word);
}
}
// Return longest string
return $result;
}
// Driver code
$dict = array("ale", "apple", "monkey", "plea");
$str = "abpcplea" ;
echo findLongestString($dict, $str);
// This code is conribued by mits
?>
Javascript
<script>
// JavaScript program to find largest word in Dictionary
// by deleting some characters of given string
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
function isSubSequence(str1, str2)
{
var m = str1.length, n = str2.length;
var j = 0; // For index of str1 (or subsequence
// Traverse str2 and str1, and compare current
// character of str2 with first unmatched char
// of str1, if matched then move ahead in str1
for (var i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
// If all characters of str1 were found in str2
return (j == m);
}
// Returns the longest string in dictionary which is a
// subsequence of str.
function findLongestString(dict, str)
{
var result = "";
var length = 0;
// Traverse through all words of dictionary
dict.forEach(word => {
// If current word is subsequence of str and is
// largest such word so far.
if (length < word.length
&& isSubSequence(word, str)) {
result = word;
length = word.length;
}
});
// Return longest string
return result;
}
// Driver program to test above function
var dict
= ["ale", "apple", "monkey", "plea"];
var str = "abpcplea";
document.write( findLongestString(dict, str));
</script>
C++
// C++ program to find largest word in Dictionary
// by deleting some characters of given string
#include <bits/stdc++.h>
using namespace std;
string res="";
void check(string d,string s)
{
int i=0;
int j=0;
while(i<d.size() && j<s.size())
{
if(d[i]==s[j])
{
i++;
j++;
}
else
j++;
}
if(i==d.size() && res.size()<d.size())
{
res=d;
}
}
string LongestWord(vector<string> d,string S) {
//sort the dictionary word
// for smallest lexicographical order
sort(d.begin(),d.end());
for(string c:d)
{
check(c,S);
}
return res;
}
// Driver program
int main()
{
vector<string> dict
= { "ale", "apple", "monkey", "plea" };
string str = "abpcplea";
cout << LongestWord(dict, str) << endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static String res="";
static void check(String d,String s){
int i = 0;
int j = 0;
while(i < d.length() && j < s.length()){
if(d.charAt(i) == s.charAt(j)){
i += 1;
j += 1;
}
else
j += 1;
if(i == d.length() && res.length() < d.length()){
res = d;
}
}
}
static String LongestWord(ArrayList<String>d,String S){
// sort the dictionary word
// for smallest lexicographical order
Collections.sort(d);
for(String c:d){
check(c,S);
}
return res;
}
// Drivers code
public static void main(String args[]){
ArrayList<String>dict = new ArrayList<String>(Arrays.asList( "ale", "apple", "monkey", "plea"));
String str = "abpcplea";
System.out.println(LongestWord(dict, str));
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to find largest word in Dictionary # by deleting some characters of given string res="" def check(d,s): global res i = 0 j = 0 while(i < len(d) and j < len(s)): if(d[i] == s[j]): i += 1 j += 1 else: j += 1 if(i == len(d) and len(res) < len(d)): res = d def LongestWord(d, S): # sort the dictionary word # for smallest lexicographical order d.sort() for c in d : check(c,S) return res # Driver program dict = [ "ale", "apple", "monkey", "plea" ] str = "abpcplea" print(LongestWord(dict, str)) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to find largest word in Dictionary
// by deleting some characters of given string
let res="";
function check(d, s)
{
let i = 0;
let j = 0;
while(i < d.length && j < s.length)
{
if(d[i] == s[j])
{
i++;
j++;
}
else
j++;
}
if(i == d.length && res.length < d.length)
{
res = d;
}
}
function LongestWord(d,S)
{
// sort the dictionary word
// for smallest lexicographical order
d.sort();
for(let c of d)
{
check(c, S);
}
return res;
}
// Driver program
let dict = [ "ale", "apple", "monkey", "plea" ];
let str = "abpcplea";
document.write(LongestWord(dict, str),"</br>");
// This code is contributed by shinjanpatra
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA