Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
public class Solution {
public int minDistance(String word1, String word2) {
if (word1.equals(word2)) {
return 0;
}
if (word1.length() == 0 || word2.length() == 0) {
return Math.abs(word1.length() – word2.length());
}
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int i = 0; i <= word2.length(); i++) {
dp[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i – 1) == word2.charAt(j – 1)) {
dp[i][j] = dp[i – 1][j – 1];
} else {
dp[i][j] =Math.min(dp[i-1][j], dp[i][j-1]) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
}
Output:
“sea”
“eat”
Answer:
2
Friendly Words:Friendly words can be defined as if a word is formed from characters of another word then those two words are friendly words.Example:listen,silent. Given an array of strings print group of friendly words in alphabetical order horizontal and vertically.
import java.util.*;
public class helloworld
{
public static void main(String []args){
String []a={“ivra”,”cheating”,”ravi”,”abc”,”cba”,”listen”,”teaching”,”dale”,”god”,”dog”,”lead”,”silent”,”deal”};
Arrays.sort(a);
String[] temp=new String[a.length];
for(int i=0;i<temp.length;i++){
temp[i]=a[i];
char[] chars = temp[i].toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
temp[i]=sorted;
}
String[] ans=new String[temp.length];
int kj=0;
Set<Integer> kh = new HashSet<>();
for(int i=0;i<temp.length;i++){
if(!kh.contains(i)){
String str=new String();
boolean matched=false;
for(int j=i+1;j<temp.length;j++){
if(temp[i].equals(temp[j])){
str=str+” “+a[j];
matched=true;
kh.add(j);
}
}
if(matched){
str=a[i]+str;
str.trim();
}
if(!str.isEmpty()&&str!=null)
ans[kj++]=str;
}
}
for(String word : ans){
if(word!=null)System.out.println(word);
}
}
}
public class helloworld
{
public static void main(String []args){
String []a={“ivra”,”cheating”,”ravi”,”abc”,”cba”,”listen”,”teaching”,”dale”,”god”,”dog”,”lead”,”silent”,”deal”};
Arrays.sort(a);
String[] temp=new String[a.length];
for(int i=0;i<temp.length;i++){
temp[i]=a[i];
char[] chars = temp[i].toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
temp[i]=sorted;
}
String[] ans=new String[temp.length];
int kj=0;
Set<Integer> kh = new HashSet<>();
for(int i=0;i<temp.length;i++){
if(!kh.contains(i)){
String str=new String();
boolean matched=false;
for(int j=i+1;j<temp.length;j++){
if(temp[i].equals(temp[j])){
str=str+” “+a[j];
matched=true;
kh.add(j);
}
}
if(matched){
str=a[i]+str;
str.trim();
}
if(!str.isEmpty()&&str!=null)
ans[kj++]=str;
}
}
for(String word : ans){
if(word!=null)System.out.println(word);
}
}
}
Output:
abc cba
cheating teaching
dale deal lead
dog god
ivra ravi
listen silent