zhizhi2007
BAN USERI agree. Instead of finding the B & C We can do a cross product of sets and put them into 2x2 array. For example, consider the following s = "a##b#c#a#b##c"
sStr = "abc"
index of a = [0, 7]
b = [3, 9]
c = [5, 12]
After cross product we have
0,3,5,
0,3,12,
0,9,5,
0,9,12,
7,3,5,
7,3,12,
7,9,5,
7,9,12,
Now finding the shortest path will be for each records, it is the total of the substraction of each number. for example take 0,3,5. It will be |0-3|+|0-5|+|3-5|=7. The smallest number is the smallest subset.
I am sure that by constructing the tree will be much efficient.
But this is the program
class TestSubmallsetString
{
static LinkedHashMap map = new LinkedHashMap();
static int[][] vvv;
public static int calc()
{
int total = 0;
int min = 99999;
int index = -1;
for (int i=0;i<vvv.length;i++)
{
for (int j=0;j<vvv[i].length;j++)
{
for (int k=j+1;k<vvv[i].length;k++)
{
total += Math.abs(vvv[i][j] - vvv[i][k]);
}
}
if (total<min)
{
index = i;
min = total;
}
total = 0;
}
return index;
}
public static void fillCrossProductArray(String s, String sStr)
{
int colIndex = 0;
int rowPointer = 0;
int tLength = vvv.length;
int counter = 0;
int tmp = 0;
for (int xx = 0; xx < sStr.length(); ++xx) // start with "a" level
{
Object[] l = ((HashSet) map.get(sStr.charAt(xx))).toArray();
for (int i1 = 0; i1 < l.length; i1++) // loop array
{
tmp =tLength / l.length;
for (int kk=rowPointer; kk < vvv.length; kk += tLength) // loop rows
{
while(counter<tmp)
{
vvv[kk+counter][colIndex] = (Integer)l[i1];
counter ++;
}
counter = 0;
}
rowPointer += tLength / l.length ;
}
tLength = tLength / l.length ;
rowPointer = 0;
colIndex ++ ;
}
}
public static void init(String s,String sStr)
{
for (int i = 0; i < sStr.length(); i++)
{
map.put(sStr.charAt(i), new LinkedHashSet());
}
for (int i = 0; i < sStr.length(); i++)
{
for (int j = 0; j < s.length(); j++)
{
if (s.charAt(j) == sStr.charAt(i))
{
((LinkedHashSet) map.get(sStr.charAt(i))).add(j);
}
}
}
Iterator it = map.keySet().iterator();
int numOfRow = 1;
HashSet hs = null;
for (int i = 0; i < map.size(); i++)
{
hs = ((LinkedHashSet) map.get(it.next()));
System.out.println(hs);
numOfRow *= hs.size();
}
vvv = new int[numOfRow][sStr.length()];
}
public static void test(String s, String sStr)
{
init(s,sStr);
fillCrossProductArray(s,sStr);
int idx=calc();
System.out.println(s);
System.out.println(sStr);
for (int i = 0; i < vvv.length; i++)
{
for (int j=0;j<vvv[i].length; j++)
{
System.out.print(vvv[i][j]+",");
}
System.out.println();
}
System.out.println("Shortest path");
for (int j=0;j<vvv[idx].length; j++)
{
System.out.print(vvv[idx][j]+",");
}
// System.out.println(s.substring((Integer)newArr.get(0),1+(Integer)newArr.get(newArr.size()-1)));
}
}
I am not sure if your solution can satisfy the requirement of the following
"Each group must contain exactly 2 or 3 digits."