Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
public class I18N {
public static void main(String[] args) {
String in = "careercup";
int count = 7;
char[] input = in.toCharArray();
String s = ""+input[0];
String e = ""+ input[input.length-1];
System.out.println(s+""+count+e);
int i =0;
while(count > 1 && i < input.length) {
--count;
System.out.println(s+input[i+1]+""+count+""+e);
System.out.println(s+""+count+input[(i+1)+count]+e);
s = s +input[i+1];
i++;
}
}
}
public static void main(String[] args) {
String in = "careercup";
int count = 7;
char[] input = in.toCharArray();
String s = ""+input[0];
String e = ""+ input[input.length-1];
System.out.println(s+""+count+e);
int i =0;
while(count > 1 && i < input.length) {
--count;
System.out.println(s+input[i+1]+""+count+""+e);
System.out.println(s+""+count+input[(i+1)+count]+e);
s = s +input[i+1];
i++;
}
}
Do you see any problem in my code ?. I could do it in one loop.
Here is a five line solution:
void printAll(string st) {
cout << st[0] << st.size()-2 << st[st.size()-1] << endl;
for(int i=st.size()-3; i>=1; i--) {
for(int k=0; k<=st.size()-2-i; k++)
cout << st.substr(0,k+1) << i << st.substr(i+k+1) << endl;
}
cout << st << endl;
}
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
public static void generateCombination(int startIndex, String inputString, int endIndex,boolean isFirst){
if(isFirst) // First Time called with generateCombination(1,input,input.length()-1, true);
{
POOSIBLE_VALUES.add(inputString); //Adding complete input String to Set
}
String startString = inputString.substring(0,startIndex);
String middleString = inputString.substring(startIndex, endIndex);
String endString = inputString.substring(endIndex, inputString.length());
String rightShift = null;
String leftShift = null;
for (int inputCounter = middleString.length(); inputCounter > 0; inputCounter--) {
if(middleString.length()==inputCounter)
{
POOSIBLE_VALUES.add(startString+inputCounter+endString);
}
else
{
rightShift = middleString.substring(0, middleString.length()-inputCounter);
POOSIBLE_VALUES.add(startString+rightShift+inputCounter+endString);
leftShift = middleString.substring(inputCounter,middleString.length());
POOSIBLE_VALUES.add(startString+inputCounter+leftShift+endString);
if(endIndex-startIndex>=2)
{
generateCombination(++startIndex, inputString, --endIndex, false);
}
}
}
}
public static void main(String[] args) {
String s = "careercup";
generateAll18(s, 1, s.length() - 1);
}
public static void generateAll18(String s, int i, int j) {
if (i >= j) {
return;
}
String s1, s2, s3;
s1 = s.substring(0, i + 1)+(j- i - 1)+""+s.substring(j, s.length());
s2 = s.substring(0, i)+(j - i)+""+s.substring(j, s.length());
s3 = s.substring(0, i+1)+(j - i)+""+s.substring(j + 1, s.length());
System.out.println(s1);
System.out.println(s2);
System.out.println(s3);
generateAll18(s, i+ 1, j-1);
generateAll18(s, i + 1, j);
generateAll18(s, i, j - 1);
}
Modify this by adding a hashtable to remove duplicates
This problem becomes simple once you break it down into processing the word layer by layer.
Maintain a prefix and suffix that start as the first and last letters of the input word.
Maintain pointers to left and right indices indicating the range of the word currently being processed.
For each "layer", we want to compute the left + sizeof(remainder to right), sizeof(remainder to left) + right, and sizeof(entire layer), then sandwich these three into the prefix and suffix computed so far, then update the prefix and suffix.
Pseudocode:
while (left < right) {
results.add(prefix + a[left] + (right - left - 1) + suffix);
results.add(prefix + (right - left - 1) + a[right] + suffix);
results.add(prefix + (right - left) + suffix);
prefix = prefix + a[left];
suffix = a[right] + suffix;
}
// It is important to identify the last layer, which is when the layer's size is 3 or 2.
// For the 2 case, left and right cross over.
// For the 3 case, left and right hit the same character, which is handled below
if (left == right) {
results.add(prefix + 1 + suffix);
prefix = prefix + a[left];
}
// Finally, add the original word into the result
results.add(prefix + suffix);
Please find the recursive solution and possibly handling all cases where the number in mid is not a single digit.
public class GenerateI18NCombination {
private Set<String> set = new HashSet<String>();
private void recurse(String arr, String strSoFar) {
if (arr.length() > 0) {
set.add(strSoFar);
String replace = replaceNumber(strSoFar, arr.length(), arr.charAt(0), true);
if (!set.contains(replace)) {
String s = arr.substring(1);
recurse(s, replace);
}
replace = replaceNumber(strSoFar, arr.length(), arr.charAt(arr.length() - 1), false);
if (!set.contains(replace)) {
String s = arr.substring(0, arr.length()-1);
recurse(s, replace);
}
} else {
set.add(strSoFar);
}
}
private String replaceNumber(String str, int length, char ch, boolean isInFront) {
String[] arr = str.split("\\d");
if (length - 1 == 0) {
return arr[0] + ch + arr[1];
} else {
if (isInFront) {
return arr[0] + ch + (length - 1) + arr[1];
} else {
return arr[0] + (length - 1) + ch + arr[1];
}
}
}
public static void main(String[] args) {
GenerateI18NCombination obj = new GenerateI18NCombination();
obj.recurse("AREERCU", "C7P");
List<String> sortedList = new ArrayList<String>(obj.set);
Collections.sort(sortedList);
System.out.println(sortedList);
}
}
public static void generateCombination(int startIndex, String inputString, int endIndex,boolean isFirst){
if(isFirst) // First Time called with generateCombination(1,input,input.length()-1, true);
{
POOSIBLE_VALUES.add(inputString); //Adding complete input String to Set
}
String startString = inputString.substring(0,startIndex);
String middleString = inputString.substring(startIndex, endIndex);
String endString = inputString.substring(endIndex, inputString.length());
String rightShift = null;
String leftShift = null;
for (int inputCounter = middleString.length(); inputCounter > 0; inputCounter--) {
if(middleString.length()==inputCounter)
{
POOSIBLE_VALUES.add(startString+inputCounter+endString);
}
else
{
rightShift = middleString.substring(0, middleString.length()-inputCounter);
POOSIBLE_VALUES.add(startString+rightShift+inputCounter+endString);
leftShift = middleString.substring(inputCounter,middleString.length());
POOSIBLE_VALUES.add(startString+inputCounter+leftShift+endString);
if(endIndex-startIndex>=2)
{
generateCombination(++startIndex, inputString, --endIndex, false);
}
}
}
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
My solution in simple words:
1. Start with a chunk size of 1
2. Iterate through position 1 through (word.length - chunk) and take out the chunk and replace it with the size of the chunk
3. Increment chunk and go to step 3 again until chunk is word.length - 2
Code:
public List<String> i18n(String word){
List<String> ret = new ArrayList<String>();
for(int chunk = 1; chunk <= word.length - 2; chunk++){
for(int i = 1; i < word.length - chunk; i++){
String s = word.substring(0, i) + chunk + word.substring(i + chunk);
ret.add(s);
}
}
return ret;
}
Here is my solution in Python.
def make_all_str(input_str):
result = []
for l in range(1, len(input_str)):
for start in range(0, len(input_str) - l + 1):
# result.append(input_str[:i] + str(len) + input_str[(start + len):]
res_str = input_str[:start] + str(l) + input_str[(start + l):]
result.append(res_str)
# end loop
# end loop
result.append(str(len(input_str)))
return result
def do_the_thing(input_str):
return map(lambda str: input_str[0] + str + input_str[-1], make_all_str(input_str[1:-1]))
print(do_the_thing("internationalization"))
def make_all_str(input_str):
result = []
for l in range(1, len(input_str)):
for start in range(0, len(input_str) - l + 1):
# result.append(input_str[:i] + str(len) + input_str[(start + len):]
res_str = input_str[:start] + str(l) + input_str[(start + l):]
result.append(res_str)
# end loop
# end loop
result.append(str(len(input_str)))
return result
def do_the_thing(input_str):
return map(lambda str: input_str[0] + str + input_str[-1], make_all_str(input_str[1:-1]))
print(do_the_thing("internationalization"))
Here is the working java code.
public class GetAllStrings
{
public static void main(String agrs[])
{
GetAllStrings("careercup");
}
private static void GetAllStrings(String iInputString)
{
for(int i=1; i<=(iInputString.length()-2); i++)
{
for(int j=1; j+i<=(iInputString.length()-1); j++)
{
System.out.print( iInputString.substring(0, j) );
System.out.print( i );
System.out.print( iInputString.substring(j+i, iInputString.length() ) );
System.out.print( "\n" );
}
}
}
}
I believe the total number of possible combinations would be 1+2+.....+(n-2) where n is the length of the string.
Sample output of above program is like
==============================
c1reercup
ca1eercup
car1ercup
care1rcup
caree1cup
career1up
careerc1p
c2eercup
ca2ercup
car2rcup
care2cup
caree2up
career2p
c3ercup
ca3rcup
car3cup
care3up
caree3p
c4rcup
ca4cup
car4up
care4p
c5cup
ca5up
car5p
c6up
ca6p
c7p
void gen_i18n(const std::string& s)
{
auto len = s.length();
for (auto i = len - 2; i >= 1; --i)
{
for (auto p = 1; p + i <= len - 1; ++p)
{
std::ostringstream oss;
oss << s.substr(0, p);
oss << i;
oss << s.substr(p + i, len - (p + i));
std::cout << oss.str() << std::endl;
}
}
std::cout << s << std::endl;
}
public static void stringManip(String inputLine){
int i,j;
int n = inputLine.length();
System.out.println(inputLine);
for(j=n;j>1;j--){
for(i =1;i<inputLine.length()-1 && (inputLine.substring(i,j-1).length() !=0);i++){
System.out.println(inputLine.substring(0,i)+""+inputLine.substring(i,j-1).length()+""+inputLine.substring(j-1));
}//end of i
}//end of j
}
public static void stringManip(String inputLine){
int i,j;
int n = inputLine.length();
System.out.println(inputLine);
for(j=n;j>1;j--){
for(i =1;i<inputLine.length()-1 && (inputLine.substring(i,j-1).length() !=0);i++){
System.out.println(inputLine.substring(0,i)+""+inputLine.substring(i,j-1).length()+""+inputLine.substring(j-1));
}//end of i
}//end of j
}
This is a lovely question that check your understanding for String processing. This is my working Java code.
import java.util.ArrayList;
import java.util.List;
public class i18nGenerator {
public static List<String> generate(String input) {
int workAreaLength = input.length() - 2;
List<String> output = new ArrayList<String>();
output.add(input);
if (input.length() <= 2) {
return output;
}
for (int i = 1; i <= workAreaLength; ++i) {
int startFrom = 1;
int windowLength = i;
while ((startFrom + windowLength) <= input.length() - 1) {
String sub1 = input.substring(0, startFrom);
String sub2 = input.substring(startFrom + windowLength);
output.add(sub1 + windowLength + sub2);
++startFrom;
}
}
return output;
}
public static void main(String []args) {
List<String> output = generate("careercup");
for (String s : output) {
System.out.println(s);
}
}
}
public void printI18NStrings(String s) {
int n = s.length() - 1;
while(n > 0) {
genStrings(s, n);
n--;
}
}
private void genStrings(String s, int n) {
int idx = 1;
String prefix = null;
String suffix = null;
while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}
public void printI18NStrings(String s) {
int n = s.length() - 1;
while(n > 0) {
genStrings(s, n);
n--;
}
}
private void genStrings(String s, int n) {
int idx = 1;
String prefix = null;
String suffix = null;
while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}
public void printI18NStrings(String s) {
int n = s.length() - 1;
while(n > 0) {
genStrings(s, n);
n--;
}
}
private void genStrings(String s, int n) {
int idx = 1;
String prefix = null;
String suffix = null;
while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}
public void printI18NStrings(String s) {
int n = s.length() - 1;
while(n > 0) {
genStrings(s, n);
n--;
}
}
private void genStrings(String s, int n) {
int idx = 1;
String prefix = null;
String suffix = null;
while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}
public void printI18NStrings(String s) {
int n = s.length() - 1;
while(n > 0) {
genStrings(s, n);
n--;
}
}
private void genStrings(String s, int n) {
int idx = 1;
String prefix = null;
String suffix = null;
while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}
import (
"fmt"
"strconv"
)
func i18n(word string) []string {
// Map to store the result
// This avoids duplicates
m := make(map[string]struct{})
for i, j := len(word)-2, 1; i > 0; i, j = i-1, j+1 {
for k := 1; k <= j; k++ {
w := word[:k] + strconv.Itoa(i) + word[i+k:]
m[w] = struct{}{}
}
}
m[word] = struct{}{}
// Extract the keys from the map
result := make([]string, len(m))
i := 0
for k := range m {
result[i] = k
i += 1
}
return result
}
private static void Printi8n(string input)
{
if (string.IsNullOrEmpty(input))
return;
int length = input.Length;
for (int i = 1; i < length; i++)
{
int substrLen = input.Substring(i, length - i - 1).Length;
string result = input.Substring(0, i) + (substrLen > 0 ? substrLen.ToString() : "") + input[length - 1];
Console.WriteLine(result);
}
}
Here is a simple C# function to do this:
private static void Printi8n(string input)
{
if (string.IsNullOrEmpty(input))
return;
int length = input.Length;
for (int i = 1; i < length; i++)
{
int substrLen = input.Substring(i, length - i - 1).Length;
string result = input.Substring(0, i) + (substrLen > 0 ? substrLen.ToString() : "") + input[length - 1];
Console.WriteLine(result);
}
}
public static void i18n(String input) {
if(input == null || input.length() < 3) {
print("Input error.");
return;
}
int ipLen = input.length();
StringBuffer buff = new StringBuffer(input);
for(int i = 1; i < ipLen - 1; i++) {
//print("replace length = " + i);
for(int k = 1; k < ipLen - i; k++) {
//print("inner loop: k = " + k);
replace(buff, k, i);
buff.setLength(0);
buff.append(input);
}
}
}
private static void replace(StringBuffer buff, int start, int len) {
buff.replace(start, start + len, String.valueOf(len));
print(buff.toString());
}
public static void print(String msg) {
if(msg != null)
System.out.println(msg);
}
I looked at this problem like a simple but unreliable string compression. Basically, each compressible word is divided into 3 parts:
1. The header
2. The body, aka the number
3. The footer
So this solution finds what I called the middle word and then finds all substrings of that middle word possible. And then for each of those, builds a possible result.
var simplifyWord = function(word){
var middleWord = word.substring(1, word.length-1);
var max = middleWord.length;
var possibleCompressions = [];
var currentWordHeader = "";
// Check if length is > 3
if(word.length < 3)
return possibleCompressions;
for(var i = 0; i < middleWord.length; i++){
var sub = "";
currentWordHeader += word[i];
for(var k = 0; k < max; k++){
sub += middleWord[i+k];
var currentWordFooter = word.substring(currentWordHeader.length + sub.length);
possibleCompressions.push(currentWordHeader + sub.length + currentWordFooter);
}
max--;
}
return possibleCompressions;
}
package crackingCode;
import java.util.ArrayList;
import java.util.List;
public class I18N {
public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}
private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();
for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
strings.add(start.toString());
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
strings.add(start.toString());
}
}
for (String s : strings) {
int numberString = subStringLength - s.length();
for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);
newStrings.add(newString);
}
}
System.out.println(newStrings);
}
}
package crackingCode;
import java.util.ArrayList;
import java.util.List;
public class I18N {
public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}
private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();
for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
strings.add(start.toString());
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
strings.add(start.toString());
}
}
for (String s : strings) {
int numberString = subStringLength - s.length();
for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);
newStrings.add(newString);
}
}
System.out.println(newStrings);
}
}
package crackingCode;
import java.util.ArrayList;
import java.util.List;
public class I18N {
public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}
private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();
for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
strings.add(start.toString());
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
strings.add(start.toString());
}
}
for (String s : strings) {
int numberString = subStringLength - s.length();
for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);
newStrings.add(newString);
}
}
System.out.println(newStrings);
}
}
/* C implementation */
void print_i18n(char *str)
{
if (!str) return;
/* minimum three character string is required */
int l = strlen(str);
if (l < 3) {
return;
}
char out[16];
/*
* Two chars are consumed by first and last positions which are
* fixed, so started with l - 2 to 1
*
* In inner loop start placing 'n' as character to each possible
* position. i.e. length of prefix (before number) + characters
* consumed by n are within limit (p + n < l)
*
* Then -
* - copy prefix (first p characters)
* - Append number
* - copy suffix after skipping n characters
*/
for (int n = l - 2; n > 0; n--) {
for (int p = 1; p + n < l; ++p) {
strncpy(out, str, p);
out[p] = '0' + n;
strcpy(out + p + 1, str + p + n);
printf("%s\n", out);
}
}
}
public class Main {
public static void main(String[] args) {
// input
String input = "LavenderFarms";
// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);
for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+ ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);
Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}
public class Main {
public static void main(String[] args) {
// input
String input = "LavenderFarms";
// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);
for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+ ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);
Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}
public class Main {
public static void main(String[] args) {
// input
String input = "LavenderFarms";
// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);
for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+ ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);
Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}
public class Main {
public static void main(String[] args) {
// input
String input = "LavenderFarms";
// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);
for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+ ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);
Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}
private void printCombination(String inputStr){
int length = inputStr.length();
int startCharCount = 2;
while(startCharCount < inputStr.length()){
Map<Integer, Integer> numberMap = getSumCombination(startCharCount++);
for(Integer key : numberMap.keySet()){
String str1 = inputStr.substring(0, key);
String str2 = inputStr.substring(inputStr.length()-numberMap.get(key), inputStr.length());
int count = inputStr.length()-(str1.length()+str2.length());
System.out.println(""+str1+"-"+count+"-"+str2);
}
}
}
/**
*
* @param startCharCount
* @return
*/
private Map getSumCombination(int startCharCount) {
int i=1;
int j=startCharCount-1;
Map numberMap = new HashMap();
numberMap.put(i, j);
while(j > 1){
numberMap.put(++i, --j);
}
return numberMap;
}
private void printCombination(String inputStr){
int length = inputStr.length();
int startCharCount = 2;
while(startCharCount < inputStr.length()){
Map<Integer, Integer> numberMap = getSumCombination(startCharCount++);
for(Integer key : numberMap.keySet()){
String str1 = inputStr.substring(0, key);
String str2 = inputStr.substring(inputStr.length()-numberMap.get(key), inputStr.length());
int count = inputStr.length()-(str1.length()+str2.length());
System.out.println(""+str1+"-"+count+"-"+str2);
}
}
}
/**
*
* @param startCharCount
* @return
*/
private Map getSumCombination(int startCharCount) {
int i=1;
int j=startCharCount-1;
Map numberMap = new HashMap();
numberMap.put(i, j);
while(j > 1){
numberMap.put(++i, --j);
}
return numberMap;
}
#include<stdio.h>
#include<string.h>
void print(char[],int);
int main()
{
char a[100],ch;
int i=0,l,len_a,j,no,b;
while((ch=getchar())!='\n')
a[i++]=ch;
a[i]='\0';
print(a,strlen(a));
}
void print(char a[],int size)
{
int b,no,i,j,l;
l=size-2;
no=1;
while(l)
{
b=no;
j=0;
while(b)
{
for(i=0;i<=j;i++)
printf("%c ",a[i]);
printf("%d ",l);
for(i=l+j+1;i<size;i++)
printf("%c ",a[i]);
printf("\n");
b--;
j++;
}
no++;
l--;
}
}
import java.util.ArrayList;
import java.util.List;
public class prog3 {
//List<String> s2 = new ArrayList<String>();
public static void main(String[] args) {
String s = "careercup";
generate_set1(s, 1, s.length());
generate_set2(s,1,s.length());
}
public static void generate_set2(String s,int i,int j)
{
if(i>=j)
{
return;
}
else
{
for(i=1;i<s.length();i++)
{
if(j-(i+2)>0)
{
String s1 =s.substring(0,i)+(j-(i+2))+s.substring(s.length()-2);
System.out.println(s1);
}
else
{
String s1 = s.substring(0,i)+s.substring(s.length()-1);
System.out.println(s1);
}
}
}
}
public static void generate_set1(String s, int i, int j) {
if (i >= j) {
return;
} else {
for (i = 1; i < s.length(); i++) {
if (j - (i + 1) > 0) {
String s1 = s.substring(0, i) + (j - (i + 1)) + s.substring(s.length() - 1);
System.out.println(s1);
} else {
String s1 = s.substring(0, i) + s.substring(s.length() - 1);
System.out.println(s1);
}
}
}
}
}
Hi I like a lot of the solutions already proposed, the idea with this one is to cache the already used strings so no need to reuse the SubString method repeatedly.
public List<string> CreateIstrings(string s)
{
List<string> result = new List<string>();
if (s == null || s.Length <= 2)
return result;
int index = 1;
int n = s.Length - 2;
string[] list1 = new string[n];
string[] list2 = new string[n];
string a = new string(s[0], 1);
string b = new string(s[s.Length - 1], 1);
for (int i = n; i >= 1; i--)
{
list1[index - 1] = a;
list2[n - index] = b;
for (int j = 0, k = n - index; j < index; j++, k++)
result.Add(list1[j] + i + list2[k]);
a += s[index];
b = s[s.Length - 1 - index] + b;
index++;
}
return result;
}
public class I18n{
public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;
for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}
public class I18n{
public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;
for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}
public class I18n{
public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;
for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}
C++ code
#include <iostream>
#include <string>
using namespace std;
void print_all(const string begin, const string middle, const string end) {
if(middle.length()==0)
cout<<begin<<end<<endl;
else {
for(int i=middle.length();i>0;i--)
cout<<begin<<i<<middle.substr(i,middle.length()-i)<<end<<endl;
print_all(begin+middle.front(),middle.substr(1,middle.length()-1),end);
}
}
int main() {
print_all("i","nternationalizatio","n");
}
#include<iostream>
#include<string>
using namespace std;
void function(string str, int count)
{
if(count<0)
return;
else if(count==0)
return;
else
{
int len = str.length();
for(int i=0;i<len-1-count;i++)
{
cout<<str[0];
for(int j=0;j<i;j++)
cout<<str[1+j];
cout<<count;
for(int j=count+1+i;j<len-1;j++)
cout<<str[j];
cout<<str[len-1];
cout<<" ";
}
cout<<endl<<endl;
if(count>=0)
function(str, count-1);
}
}
int main()
{
string str = "careercup";
function(str, str.length()-2);
system("PAUSE");
return 0;
}
void printPermutations(string str, int head, int gap) {
for (int i = 0; i < head;i++) {
cout << str[i];
}
cout << gap;
for (int i = head + gap; i < str.size(); i++) {
cout << str[i];
}
cout << "\n";
}
void getPermutations(string str, int gap) {
int head = 1;
int tail = gap;
while (tail < str.size() - 1) {
printPermutations(str, head, gap);
head++;
tail++;
}
}
void i18n(string str) {
for (int i = str.size() - 2; i > 0; i--;) {
getPermutations(str, i);
}
}
594 void print_i18n(char *S, int i, int j, int n) {
595
596 int k=0;
597
598 while(k<=i){
599 printf("%c", S[k]);
600 k++;
601 }
602 printf("%d", j-(i+1));
603 while(j<=n){
604 printf("%c", S[j]);
605 j++;
606 }
607 printf("\n");
608 }
609
610 void i18n(char *S, int i, int j, int n) {
611
612 if(j-i == 1)
613 return;
614
615 print_i18n(S, i, j, n);
616
617 i18n(S, i+1, j, n);
618 i18n(S, i, j-1, n);
619
}
call this function like this : i18n(S, 0, n-1, n-1);
where n is length of the string
function abbreviations($s){
$middle = substr($s, 1, strlen($s) - 2);
for($i=1; $i<strlen($s)-2; $i++){
echo $s[0] . substr($middle, 0, $i) . (strlen($s)-2 - $i) . $s[strlen($s)-1] . '<br/>';
echo $s[0] . (strlen($s)-2 - $i) . substr($middle, strlen($s)-2 - $i, $i) . $s[strlen($s)-1] . '<br/>';
}
echo $s[0] . ( strlen($s) - 2) . $s[strlen($s)-1];
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}
Not sure if somebody has already suggested this approach, we can easily solve this by recursion.
We also need to maintain a hash table to eliminate duplicates
The pseudo code would be as follows
generatei18n(str, sPos, ePos){
i = (ePos - sPos) - 1
if( i <= 0) return
rs = str.subString(0,sPos)+ i + str.subString(ePos);
generatei18n(str, sPos+1, ePos)
generatei18n(str, sPos, ePos-1)
}
The time complexity would be !n.
Here is a five line code solution for the problem:
- Sanchit Gupta May 22, 2015