Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
this will return the EMPTY set (i.e. "") which should be skipped according to the example above
Guess it was posted after the question was updated to say order doesn't matter, otherwise the vote wouldn't be so high.
how about this?
public static void Combinations(char[] arr, List<string> wordList, string pre, int idx)
{
for (int i = idx; i < arr.Length; i++)
{
string currWord = pre + arr[i];
if (!wordList.Contains(currWord))
{
wordList.Add(currWord);
Console.WriteLine(currWord);
Combinations(arr, wordList, currWord, i + 1);
}
}
}
static void Main(string[] args)
{
Combinations(new char[] { 'a', 'b', 'a', 'b', 'a', 'b' /*'c' */}, new List<string>(), string.Empty, 0);
Console.Read();
}
public static List<String> getSubStrings(String word) {
List<String> allSubStrings = new ArrayList<String>();
int max = 1 << word.length();
for (int index = 1; index < max; index++) {
StringBuffer subString = new StringBuffer();
int bits = index;
int _index = 0;
while (bits > 0) {
if ((bits & 1) > 0) {
subString.append(word.charAt(_index));
}
bits >>= 1;
_index++;
}
allSubStrings.add(subString.toString());
}
return allSubStrings;
}
public static void main(String[] args) {
String word = "abc";
System.out.println(getSubStrings(word));
String word1 = "abababab";
System.out.println(getSubStrings(word1));
}
Well, think of each possible substring of the original string is a array of the same size of original string, if the character is included in the substring , the corresponding digit is 1, else is 0 for example, string "abcd" substring "ad" then binary form is 1001 ,print all the possible (2^n) binary array with function recursion, each postion in the binary array there are onyl 2 possibilties.
Here is the non-recursive implementation in C++.
void print_all_substrings_iterative(const std::string& str)
{
const size_t size = str.size();
for (size_t i = 1; i < std::pow(2.0, (double)size); ++i) {
for (size_t j = 0; j < size; ++j) {
if (i & (1 << j)) {
std::cout << str[j];
}
}
std::cout << ' ';
}
std::cout << std::endl;
}
public ArrayList<String> permutations(String s){
if(s == null){
return null;
}
ArrayList<String> result = new ArrayList<String>();
if(s.length()==1){
result.add(s);
return result;
}
String firstTwo = s.substring(0,2);
result.add(firstTwo);
result.add(""+s.charAt(1)+s.charAt(0));
//System.out.println(""+s.charAt(1)+s.charAt(0));
for(int i = 2; i<s.length();i++){
char c = s.charAt(i);
result = insertChar(c,result);
}
Iterator<String> it = result.iterator();
while(it.hasNext())
{
System.out.print(it.next()+" ");
}
return result;
}
private ArrayList<String> insertChar(char c,ArrayList<String> list){
ArrayList<String> tempResult = new ArrayList<String>();
Iterator<String> it = list.iterator();
while(it.hasNext()){
String temp = it.next();
for(int i = 0; i<=temp.length(); i++){
String toBeAdded = temp.substring(0, i)+c+temp.substring(i);
tempResult.add(toBeAdded);
}
}
return tempResult;
}
I think we should consider the scenario that there are duplicated characters. (Ex. "abcc")
My idea is:
(1) count the number of distinct characters (3: a,b,c)
(2) count the occurence of each characters (a: 1, b: 1, c: 2)
(3) each character could be chosen [0 ~ occurence] times (a: 0~1, b:0~1, c:0~2)
The following is my implementation together with some simple tests:
import java.util.*;
class G210
{
public static ArrayList<String> allSubstring(String input)
{
ArrayList<String> list = new ArrayList<String>();
if (null == input) {return list;}
if (0 == input.length()) {return list;}
// count the number of distinct characters
char[] chars = input.toCharArray();
Arrays.sort(chars);
int type = 1;
char last = chars[0];
for (int i = 1; i < chars.length; i++) if (chars[i] != last)
{
type++;
last = chars[i];
}
// count the occurence of each characters
char[] candidates = new char[type];
int[] limits = new int[type];
type = 0; last = chars[0];
int count = 1;
for (int i = 1; i < chars.length; i++)
{
if (chars[i] != last)
{
candidates[type] = last;
limits[type] = count;
type++;
last = chars[i];
count = 1;
}
else {count++;}
}
candidates[type] = last;
limits[type] = count;
// each character could be chosen [0 ~ occurence] times
int[] counts = new int[limits.length];
while (next(counts, limits))
{
StringBuffer sb = new StringBuffer();
for (int i = 0; i < candidates.length; i++)
for (int j = 0; j < counts[i]; j++)
{
sb.append(candidates[i]);
}
list.add(sb.toString());
}
return list;
}
private static boolean next(int[] counts, int[] limits)
{
for (int i = counts.length - 1; i >= 0; i--)
{
counts[i]++;
if (counts[i] <= limits[i]) {return true;}
counts[i] = 0;
}
return false;
}
public static void main(String[] args)
{
System.out.println("set1 = " + allSubstring("abc"));
System.out.println("set2 = " + allSubstring("abcd"));
System.out.println("set3 = " + allSubstring("abcc"));
}
}
public static List<String> getSubStrings(String word) {
List<String> allSubStrings = new ArrayList<String>();
int max = 1 << word.length();
for (int index = 1; index < max; index++) {
StringBuffer subString = new StringBuffer();
int bits = index;
int _index = 0;
while (bits > 0) {
if ((bits & 1) > 0) {
subString.append(word.charAt(_index));
}
bits >>= 1;
_index++;
}
allSubStrings.add(subString.toString());
}
return allSubStrings;
}
public static void main(String[] args) {
String word = "abc";
System.out.println(getSubStrings(word));
}
public static Set<String> subStrs(String str, int from, int to){
if(from == to){
Set<String> ret = new HashSet<String>();
ret.add("");
ret.add(String.valueOf(str.charAt(from)));
return ret;
}
Set<String> ret1 = subStrs(str, from + 1, to);
Set<String> ret2 = new HashSet<String>();
Iterator<String> iter = ret1.iterator();
while(iter.hasNext()){
String tmp = iter.next();
iter.remove();
String tmp1 = tmp + str.substring(from, from + 1);
if(from == 0){
if(tmp != "")
ret2.add(tmp);
}else{
ret2.add(tmp);
}
ret2.add(tmp1);
}
return ret2;
}
import java.util.ArrayList;
import java.util.List;
public class SubstringGenerator {
public SubstringGenerator(String str) {
super();
this.str = str;
}
private final String str;
public List<String> generate(){
List<String> allSubstrings = new ArrayList<>();
for( int index = 0; index < str.length(); index++ ){
allSubstrings.addAll( generateRight(str, "", index) );
}
return allSubstrings;
}
private List<String> generateRight(String base, String prefix, int fromIndex){
String curPrefix = prefix + base.charAt(fromIndex);
List<String> substrings = new ArrayList<String>();
substrings.add( curPrefix );
for( int offset = fromIndex+1; offset < base.length(); offset++ ){
substrings.addAll( generateRight(base, curPrefix, offset));
}
return substrings;
}
}
void allsubstrings(string str,int st_index,int end_index, vector<string>& strvector)
{
string st1,st2;
vector<string> tempvector;
vector<string>::iterator it;
if(st_index == end_index)
{
st1.push_back(str[st_index]);
strvector.push_back(st1);
}
else
{
allsubstrings(str,st_index+1,end_index,strvector);
for(it = strvector.begin(); it != strvector.end(); ++it)
{
st2 = *it;
st2 += str[st_index];
tempvector.push_back(st2);
st2.clear();
}
st1.push_back(str[st_index]);
tempvector.push_back(st1);
strvector.insert( strvector.end(), tempvector.begin(), tempvector.end() );
}
}
strvector contains all the substrings of the string str
View the input as a bit vector. Then, it is about enumerating a bit vector of size n.
Idea:
Input: "cab"
1. Recursively call the function each time trimming one character (trim c, then a)
2. When the length of the string reaches 1, return an empty string and one length character. Like ("", "b")
3. For each of the item returned from the recursion, create two items: 1. same item 2. add the trimmed character
Like: ("", "a", "b", "ab")
4. At the end, we will have all the combinations.
Here is the python code:
1 #! /usr/bin/env python
2 import sys
3
4 def generateCombination(inp):
5 if len(inp) == 1:
6 return [[],[inp[0]]]
7
8 myContrib = inp[0]
9 rest = generateCombination(inp[1:])
10 result = []
11 for aCombination in rest:
12 s = aCombination[:]
13 t = aCombination[:]
14 t.append(myContrib)
15 result.append(s)
16 result.append(t)
17
18 return result
19
20 if __name__ == '__main__':
21 inp = map(lambda x : int(x), sys.argv[1].split(" "))
22 result = generateCombination(inp)
23 for anItem in result:
24 print anItem
import java.util.*;
public class Solution2
{
public static void main(String arg[])
{
Vector result=new Vector();
String data="abc";
for(int i=0;i<data.length();i++)
{
for(int j=i;j<=data.length();j++)
{
if(!result.contains(data.substring(i,j)))
result.add(data.substring(i,j));
}
}
for(int i=0;i<result.size();i++)
System.out.print((String)result.elementAt(i) + " ");
}
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
import java.lang.Math;
class Permutations
{
public static void main (String args[])
{
if (args.length != 1)
{
System.out.println ("Enter one string");
return;
}
String str = args[0];
int pow = str.length();
int max = (int)Math.pow (2, pow);
for (int i=0; i< max; i++)
{
StringBuilder builder = new StringBuilder();
int mask = 1;
for (int j=0; j<str.length(); j++)
{
if ( (i & mask) != 0)
{
builder.append (str.charAt(j));
}
mask = mask << 1;
}
System.out.println (builder.toString());
}
}
}
The substring of the given string matchs below numbers
0 0 1 -- a
0 1 0 -- b
0 1 1 -- ab
1 0 0 -- c
1 0 1 -- ac
1 1 0 -- bc
1 1 1 -- abc
/// C++ code below
void print(char * str, int s)
{
int one = 1;
int i = 0, len = strlen(str);
for(i = 0; i < len; i ++)
{
if(s & (one << i)) cout<<str[i];
}
cout<<endl;
}
int generate_substring(char * str)
{
if(NULL == str) return -1;
int s = 1, len = strlen(str);
while(len)
{
s *= 2;
len --;
}
s -= 1;
while(s)
{
print(str, s);
s --;
}
return 0;
}
private static String generateSubstrings(String input)
{
String output = "{ ";
for(int x = 1; x <= input.length(); x++)
{
for(int y = 0; y+x <= input.length(); y++)
{
output += (input.substring(y, y+x) + ", ");
}
}
//remove last ', '
output = output.substring(0, output.length()-2);
output += " }";
return output;
}
public static final String[] generateSubsets(String input) {
int length = input.length();
int size = (int) Math.pow(2, length);
BitSet[] sets = new BitSet[size];
String[] output = new String[size];
for (int i=0; i<size; i++) {
BitSet set = new BitSet(size);
StringBuilder builder = new StringBuilder();
if (i>0) {
for (int j=length-1; j>=0; j--) {
if (j==length-1) {
if (i%2!=0) set.set(j, true);
} else {
boolean prev = sets[i-1].get(j);
boolean next = true;
for (int k=j+1; k<length; k++) {
next = next && sets[i-1].get(k);
}
if (next) prev = !prev;
set.set(j, prev);
}
if (set.get(j)) builder.append(input.charAt(j));
}
}
sets[i] = set;
output[i] = builder.toString();
}
return output;
}
public static final String[] generateSubsets(String input) {
int length = input.length();
int size = (int) Math.pow(2, length);
BitSet[] sets = new BitSet[size];
String[] output = new String[size];
for (int i=0; i<size; i++) {
BitSet set = new BitSet(size);
StringBuilder builder = new StringBuilder();
if (i>0) {
for (int j=length-1; j>=0; j--) {
if (j==length-1) {
if (i%2!=0) set.set(j, true);
} else {
boolean prev = sets[i-1].get(j);
boolean next = true;
for (int k=j+1; k<length; k++) {
next = next && sets[i-1].get(k);
}
if (next) prev = !prev;
set.set(j, prev);
}
if (set.get(j)) builder.append(input.charAt(j));
}
}
sets[i] = set;
output[i] = builder.toString();
}
return output;
}
----------------Recursive Solution----------------------
recFindSubSets("", "abc");
public static ArrayList<String> recFindSubSets(String str1, String str2){
ArrayList<String> subSets = new ArrayList<String>();
if(str2.length() == 0){
subSets.add(str1);
return subSets;
}
ArrayList<String> subSets1 = recFindSubSets(str1 + str2.substring(0, 1), str2.substring(1, str2.length()));
ArrayList<String> subSets2 = recFindSubSets(str1, str2.substring(1, str2.length()));
subSets.addAll(subSets1);
subSets.addAll(subSets2);
return subSets;
}
------------Non Recursive Solution-----------------
nonRecFindSubSets("abc");
public static ArrayList<String> nonRecFindSubSets(String str){
ArrayList<String> subSets = new ArrayList<String>();
int len = str.length();
int totalSets = (int) Math.pow(2, len) - 1;
StringBuilder str1 = new StringBuilder();
for(int i=totalSets; i>=0; i--){
str1.delete(0, str1.length());
int bitmask = (int) Math.pow(2, len-1);
for(int j=0;j<len; j++) {
if((i & bitmask) > 0){
str1.append(str.charAt(j));
}
bitmask = bitmask >> 1;
}
subSets.add(str1.toString());
}
return subSets;
}
private static void GenSubstrings(string input)
{
int len = 0;
Console.Write("{");
//Iterate through all letters of the input string
for (int i = 0; i < input.Length; i++)
{
len = input.Length - i;
//If the current letter not the last letter of the input string
if (i != input.Length - 1) {
//Generate all substring combinations starting with the letter
for (int j = 1; j <= len; j++) {
Console.Write(input.Substring(i, j) + ",");
}
} else {
Console.Write(input.Substring(i, 1));
}
}
Console.Write("}");
}
public static void listStrings(byte[] x, int num, int sb_index, StringBuffer sb)
{
if( num >= x.length )
{
return;
}
sb.append((char)x[num]);
System.out.println(sb.toString());
for(int i=num+1;i<x.length;i++)
{
listStrings(x,i,sb_index+1,sb);
}
sb.setLength(sb_index);
}
public static void main(String[] arg)
{
byte x[] = "abc".getBytes();
StringBuffer sb = new StringBuffer();
for(int i=0;i<x.length;i++)
{
listStrings(x,i,0,sb);
}
}
public class Combination
{
public static void main(String[] args)
{
String input = "ABC";
StringBuffer sb = new StringBuffer();
combination(input.toCharArray(), 0, input.length() - 1, sb);
}
public static void combination(char[] arr, int a, int b, StringBuffer sb)
{
for (int i = a; i <= b; i++)
{
sb.append(arr[i]);
System.out.println(sb);
combination(arr,i+1, b, sb);
sb.setLength(sb.length()-1);
}
}
}
public class Test
{
public static void main(String[] args)
{
printAll("ABC", 0, new StringBuffer());
// Outputs
// ---------
// A
// AB
// ABC
// AC
// B
// BC
// C
}
private static void printAll(String str,int start, StringBuffer sb)
{
for(int i=start; i< str.length(); i++)
{
sb.append(str.charAt(i));
System.out.println(sb);
printAll(str, i+1, sb);
sb.setLength(sb.length()-1);
}
}
}
#include<stdio.h>
#include<stdlib.h>
struct node
{
char c;
struct node* next;
struct node* prev;
};
struct node* addnode(struct node* head,char data)
{
if(!head)
{
head=(struct node*)malloc(sizeof(struct node));
if(!head)
return NULL;
head->c=data;
head->next=head;
head->prev=head;
}
else
{
struct node* tmp=head;
struct node* tmp1=head;
struct node* newn;
while(tmp->next!=tmp1) tmp=tmp->next;
newn=(struct node*)malloc(sizeof(struct node));
if(!newn)
return NULL;
tmp->next=newn;
newn->c=data;
newn->next=tmp1;
newn->prev=tmp;
tmp1->prev=newn;
}
return head;
}
void printnode(struct node* head)
{
struct node* tmp=head;
struct node* tmp1=head;
do
{
printf("%c->",tmp->c);
tmp=tmp->next;
}while(tmp!=tmp1);
tmp=head;
tmp1=head;
do
{
printf("%c->",tmp->c);
tmp=tmp->prev;
}while(tmp!=tmp1);
printf("\n");
}
int main()
{
char* name="abcd";
struct node* head=NULL;
while(*name!='\0')
{
head=addnode(head,*name);
name++;
}
//printnode(head);
struct node* t1=head;
struct node* t2=head;
struct node* t3=head;
do
{
do
{
do
{
printf("%c",t2->c);
t2=t2->next;
}while(t2!=t3);
printf(",");
t2=t1;
t3=t3->prev;
}while(t3!=t1->next);
t3=t1;
do
{
do
{
printf("%c",t2->c);
t2=t2->prev;
}while(t2!=t3);
printf(",");
t2=t1;
t3=t3->next;
}while(t3!=t1);
t1=t1->next;
t2=t1;
t3=t1;
}while(t1!=head);
printf("\n");
return 0;
}
It seems to me that a non-recursive solution is better because:
a) easily avoid extra substring calls (which creates extra copies of string)
b) avoid printing or storing of duplicate result. I don't see a good way to avoid duplicate calls when doing it recursively
def allsubstrshelper(s, startindex):
print s[startindex]
for i in range(startindex + 1, len(s)):
print(s[startindex:i+1])
def allsubstrs(s):
for i in range(len(s)):
allsubstrshelper(s, i)
allsubstrs("abcd") prints:
a
ab
abc
abcd
b
bc
bcd
c
cd
d
vector<string> permutation (string str)
{
int len = str.length();
vector<bool> used;
used.assign(len, false);
vector<string> result;
string current =””;
addNext (current, used, str, result);
}
void addNext (string current, vector<bool> used, string candidates, vector<string> & result)
{
if(current.size > 0)
result.push_back(current);
int size = used.size();
for (int i = 0; i< size; i++)
{
if (used[i])
continue;
used[i] = true;
addNext(current+candidates, used, candidates, result);
used[i] = false;
}
}
public static void main(String[] args) {
char[] c = "abcb".toCharArray();
System.out.println(getAllSubstrings(c, 0, ""));
}
private static Set<MyString> getAllSubstrings(char[] c, int i, String prefix) {
Set<MyString> s = new HashSet<MyString>();
if (i < c.length) {
s.add(new MyString(prefix + c[i]));
s.addAll(getAllSubstrings(c, i + 1, "" + c[i]));
s.addAll(getAllSubstrings(c, i + 1, prefix + c[i]));
}
s.add(new MyString(prefix));
return s;
}
static class MyString {
private final String s;
private final String sortedS;
public MyString(String s) {
super();
this.s = s;
char[] c = s.toCharArray();
Arrays.sort(c);
sortedS = new String(c);
}
public String getS() {
return s;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((sortedS == null) ? 0 : sortedS.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MyString other = (MyString) obj;
if (sortedS == null) {
if (other.sortedS != null)
return false;
} else if (!sortedS.equals(other.sortedS))
return false;
return true;
}
@Override
public String toString() {
return s;
}
}
Below is the implementation in Java.
Iterative:
public static Set<String> getSubStringsIter(String input) {
Set<String> res = new HashSet<>();
if (input == null || input.isEmpty()) {
return res;
}
res.add("");
for (char c : input.toCharArray()) {
Set<String> resCopy = new HashSet<>();
for (String string : res) {
resCopy.add(string + c);
}
res.addAll(resCopy);
}
res.remove("");
return res;
}
Recursive Approach:
public static Set<String> getSubStringsRecursive(String input) {
if(input == null) {
return null;
}
Set<String> res = getSubStringsRecursiveHelper(input);
res.remove("");
return res;
}
public static Set<String> getSubStringsRecursiveHelper(String input) {
if (input.isEmpty()) {
return new HashSet<>(Arrays.asList(input));
}
Set<String> mergeResult = merge(input.substring(0,1), getSubStringsRecursiveHelper(input.substring(1)));
return mergeResult;
}
private static Set<String> merge(String substring, Set<String> res) {
Set<String> copy = new HashSet<>();
for (String string : res) {
copy.add(substring + string);
}
res.addAll(copy);
return res;
}
JUnit:
@Test
public void test_getSubStrings() {
String input = "abc";
Set<String> expectedRes = new HashSet<>(Arrays.asList("a","b","c","ab", "ac", "bc", "abc"));
Set<String> subStringsIter = InterviewQuestions.getSubStringsIter(input);
Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsIter.size());
Assert.assertEquals(expectedRes, subStringsIter);
Set<String> subStringsRecursiveRes = InterviewQuestions.getSubStringsRecursive(input);
Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsRecursiveRes.size());
Assert.assertEquals(expectedRes, subStringsRecursiveRes);
}
int main(){
int n;
int q;
cin >> n >> q;
string s;
cin >> s;
for(int a0 = 0; a0 < q; a0++){
int left;
int right;
cin >> left >> right;
set<string> insignificant;
for(int i = left; i <= right; i++){
string temp;
for (int j = i; j <= right; ++j){
temp += s[j];
set< string >::iterator it = insignificant.find(temp);
if (it == insignificant.end())
insignificant.insert(temp);
}
}
cout<<insignificant.size()<<endl;
for (set<string>::iterator it = insignificant.begin(); it != insignificant.end(); it++)
cout<<*it<<" ";
}
return 0;
}
Recursive C solution for the same
#include <stdio.h>
char Arr[] = "abcde";
int n = 5; //length of above string
void printforward(char fromPrev[6], int start, int position){
for(int i = start; i<n;i++){
fromPrev[position] = Arr[i];
fromPrev[position+1] = '\0';
printf("%s\n", fromPrev);
printforward(fromPrev, i+1, position+1);
}
}
int main(void) {
for(int i=0; i<n;i++){
char fromPrev[6];
printf("%c\n",Arr[i]);
fromPrev[0] = Arr[i];
printforward(fromPrev,i+1,1);
}
return 0;
}
P.S.: I know Arr and its length should not be declared global.
Let’s assume a given string S represented by the letters A1, A2, A3, ... , An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list
Now, the code to do this:
public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) { // error case
return null;
} else if (s.length() == 0) { // base case
permutations.add(“”);
return permutations;
}
char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
permutations.add(insertCharAt(word, first, j));
}
}
return permutations;
}
public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}
This solution takes O(n!) time, since there are n! permutations.
Guess you are returning all the permutations, when that is not what is asked. So, bc <=> cb., and so on for others.
And, I guess there should be total of 2^n strings. not n!
- loveCoding January 24, 2012