CareerCup

here is my solution which (I believe) works correctly and also prints the sequence

package info.hevi.interviews.google.questions;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: uerturk
 * Date: 08/10/13
 * Time: 17:04
 * To change this template use File | Settings | File Templates.
 */
public class HasChain {

    Map<Character, List<String>> startsWith = new HashMap<Character, List<String>>();
    Map<Character, List<String>> endsWith = new HashMap<Character, List<String>>();

    private Character getFirstChar(String str) {
        return str.charAt(0);
    }

    private Character getLastChar(String str) {
        return str.charAt(str.length() - 1);
    }

    boolean hasChain(List<String> stringList) {
        for (String str : stringList) {
            Character start = getFirstChar(str);
            Character end = getLastChar(str);
            List<String> startsWithList;
            List<String> endsWithList;

            if (startsWith.containsKey(start)) {
                startsWithList = startsWith.get(start);
            } else {
                startsWithList = new ArrayList<String>();
                startsWith.put(start, startsWithList);
            }

            if (endsWith.containsKey(end)) {
                endsWithList = endsWith.get(end);
            } else {
                endsWithList = new ArrayList<String>();
                endsWith.put(end, endsWithList);
            }
            startsWithList.add(str);
            endsWithList.add(str);
        }

        Stack<String> stringStack = new Stack<String>();
        for (String str : stringList) {
            if (hasChain(stringList.size(), str, stringStack)) {
                System.out.println(stringStack);

                return true;
            }
        }

        return false;
    }

    private boolean hasChain(int size, String startString, Stack<String> stringStack) {
        if (size == stringStack.size()) return true;
        Character last = getLastChar(startString);
        if (startsWith.containsKey(last)) {
            List<String> stringList = startsWith.get(last);
            for (int i = 0; i < stringList.size(); i++) {
                String candidate = stringList.remove(i--);
                stringStack.push(candidate);
                if (hasChain(size, candidate, stringStack)) {
                    return true;
                }
                stringStack.pop();
                stringList.add(++i, candidate);
            }
        }

        return false;
    }

    public static void main(String[] args) {
        List<String> stringList = new ArrayList<String>();
        stringList.add("bd");
        stringList.add("fk");
        stringList.add("ab");
        stringList.add("kl");
        stringList.add("cf");
        stringList.add("ff");
        stringList.add("fa");
        stringList.add("ak");
        stringList.add("ka");
        stringList.add("lf");
        stringList.add("bc");

        System.out.println(new HasChain().hasChain(stringList));

        stringList.remove("ka");

        System.out.println(new HasChain().hasChain(stringList));

    }
}

public static boolean chaintermed(String[] strings){
NodePP[] arr=new NodePP[26];
int count=0;
for(int i=0;i<strings.length;i++){
int pre=strings[i].charAt(0)-'a';
int pro=strings[i].charAt(strings[i].length()-1)-'a';
if(arr[pre]==null){
NodePP nPre=new NodePP();
arr[pre]=nPre;
}
if(arr[pro]==null){
NodePP nPro=new NodePP();
arr[pro]=nPro;
}
arr[pre].pre++;
arr[pro].pro++;
}
for(int j=0;j<strings.length;j++){
int pre=arr[strings[j].charAt(0)-'a'].pro;
int pro=arr[strings[j].charAt(strings[j].length()-1)-'a'].pre;
if(((pre==0)&&(pro==0))){return false;}
if((pre!=pro)){
count++;
}
}
return count==2?true:false;
}

In the perfect case the posed problem would be resolved with a graph and searching for Hamiltonian path, which is NP-complete, so I avoided graph and did a brute-force solution: build all combinations of strings recursively and return false if it fails to build the combination at any level, here's working code:

bool validChain(std::vector<std::string*> &newChain) {
    if(newChain.size() <= 1) return true;
    for(int i = 1; i < newChain.size(); ++i) {
        std::string *prevString = newChain[i-1];
        if((*newChain[i])[0] != (*prevString)[prevString->size() - 1]) {
            return false;
        }
    }
    return true;
}

bool isChainable(std::vector<std::string*>::iterator start,
                 std::vector<std::string*>::iterator end,
                 std::vector<std::vector<std::string*>> &chains) {
    if(std::distance(start, end) == 1) {
        std::vector<std::string*> singleChain({*start});
        chains.push_back(singleChain);
        return true;
    }

    std::string *head = *start;
    std::vector<std::vector<std::string*>> tmpChains;
    if(isChainable(++start, end, tmpChains)) {
        for(std::vector<std::string*> chain : tmpChains) {
            for(int i = 0; i <= tmpChains.size(); ++i) {
                std::vector<std::string*> newChain(chain.size() + 1);
                newChain[i] = head;
                std::copy(chain.begin(), chain.begin() + i, newChain.begin());
                std::copy(chain.begin() + i, chain.end(), newChain.begin() + i + 1);
                if(validChain(newChain)) chains.push_back(newChain);
            }
        }
    }
    return chains.size() > 0;
}

bool isChainable(std::vector<std::string*> arr) {
    std::vector<std::vector<std::string*>> chains;
    return isChainable(arr.begin(), arr.end(), chains);
}

int main()
{
    std::string str1("abc"), str2("feg"), str3("cef");
    std::cout << isChainable(std::vector<std::string*>({&str1, &str2, &str3}));

    return 0;
}

Hi please let me know if the following is failing for any test case:

#include <stdio.h>
#include <stdlib.h>

struct list{
int v;
int indegree;
struct list *next;
};

struct Graph{
int V;
struct list **Adj;
};

struct Graph *createG(int n){
int i=0,j=0;
struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph));

G->V=n;

G->Adj=(struct list**)malloc(sizeof(struct list*)*n*2);

for(j=0;j<n;j++){
G->Adj[i]=(struct list*)malloc(sizeof(struct list));

G->Adj[i]->v=i;
G->Adj[i]->indegree=0;



G->Adj[i+1]=(struct list*)malloc(sizeof(struct list));
G->Adj[i+1]->v=i+1;

G->Adj[i+1]->indegree=0;



struct list *temp=(struct list*)malloc(sizeof(struct list));
temp->v=i+1;
temp->next=NULL;
G->Adj[i]->next=temp;

struct list *temp2=(struct list*)malloc(sizeof(struct list));
temp2->v=i;
temp2->next=NULL;
G->Adj[i+1]->next=temp2;



i+=2;
}



return G;

}

void createEdge(struct Graph *G,struct list *u,struct list *v){
int p,q;

p=u->v;
q=v->v;

struct list *temp=(struct list*)malloc(sizeof(struct list));
temp->v=q;
temp->next=G->Adj[p]->next;
G->Adj[p]->next=temp;
G->Adj[p]->indegree+=1;

struct list *temp2=(struct list*)malloc(sizeof(struct list));
temp2->v=p;
temp2->next=G->Adj[q]->next;
G->Adj[q]->next=temp2;
G->Adj[q]->indegree+=1;

return;



}

struct list_t{
char key;
struct list *val;
struct list_t *next;
};


struct hash_table{
int size;
struct list_t **table;
};

struct hash_table *createH(int size){
int i;
struct hash_table *t=(struct hash_table*)malloc(sizeof(struct hash_table));

t->size=size;

t->table=(struct list_t**)malloc(sizeof(struct list_t)*size);

for(i=0;i<size;i++)
t->table[i]=NULL;

return t;
}


int hash(struct hash_table *t,char key){
unsigned int hashval=0;

hashval=((int)key)<<5 -(int)key;

return hashval%t->size;

}


struct node{
struct list *v;
struct node *next;

};

void Insert(struct node **head,struct list *v){
struct node *temp=(struct node*)malloc(sizeof(struct node));

temp->v=v;

temp->next=*head;
*head=temp;

}


struct list *lookupH(struct hash_table *t,char key){

int hashval=hash(t,key);

struct list_t *list_val=NULL;

struct node *head=NULL;

for(list_val=t->table[hashval];list_val;list_val=list_val->next){
if(list_val->key==key)
Insert(&head,list_val->val);
}

return head;
}

void InsertH(struct hash_table *t,char key,struct list *val){


int hashval=hash(t,key);

struct list_t *list_val=(struct list_t*)malloc(sizeof(struct list_t));

list_val->key=key;
list_val->val=val;

list_val->next=t->table[hashval];

t->table[hashval]=list_val;


}


int main()
{

int i,j=0,n;
printf("Enter # of strings\n");

scanf("%d",&n);

char **A=(char**)malloc(sizeof(char*)*n);

for(i=0;i<n;i++){
printf("Enter string # %d\n",i+1);
A[i]=(char*)malloc(sizeof(char)*20);
scanf("%s",A[i]);
}

struct Graph *G=createG(n);


struct hash_table *t1=createH(n);
struct hash_table *t2=createH(n);

j=0;



for(i=0;i<n;i++){
int len=strlen(A[i]);

InsertH(t1,*(A[i]),G->Adj[j]);

struct node *head=lookupH(t2,*(A[i]));

while(head){
createEdge(G,G->Adj[j],head->v);
head=head->next;
}


InsertH(t2,*(A[i]+len-1),G->Adj[j+1]);


head=lookupH(t1,*(A[i]+len-1));


while(head){
createEdge(G,G->Adj[j+1],head->v);
head=head->next;
}



j+=2;

}

j=0;
int count1=0,count2=0;


for(i=0;i<n;i++){
if(G->Adj[j]->indegree==0)
count1++;
if(G->Adj[j+1]->indegree==0)
count2++;
j+=2;
}



if(count1>1 || count2>1)
printf("NO");
else
printf("YES");

return 0;
}

Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.

Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.

Can I use bucket sort? Create 1 array each with 26 entries. All strings will first character a in the 0th entry, b in 1st entry and so on. It takes O(n) to create such an array.
Now we traverse the array once, pop the just word we encounter in the array, read its last character, pop the first string with that character in corresponding entry of the array. Keep doing it until there are no more string in the array. This procedure also takes O(n) times.
Total run time is O(n).

We can also use a hash table:

for(i=0;i<NumStrings;i++)
  table[s[i].at(0)]=i; // this can be modified to contain a chain of i values to address overlapping starting characters between different strings
for(i=0;i<NumStrings;i++)
{
  if(table[s[i].at(s[i].size()-1)]!=-1 && i!=table[s[i].at(s[i].size()-1)])
     Code to Append String at index i and String at index table[s[i].at(s[i].size()-1)]
}

#include <iostream>
#include <string>
using namespace std;


int main() {

string in[] ={"adsd", "qasdasdb", "ndasdf", "aasddq", "fasda", "deasdn", "oooa"};
int n = 7;
int a[26] ={};

for(int i =0; i<n; i++) {
	int s = (in[i][0])-97;
	int e =	(in[i][(in[i].length()-1)])-97;
	a[s]++;
	if(s != e) {		
		a[e]++;
	}
}
int count =0;
for(int i =0; i<26; i++){
	if(a[i]%2 !=0) count++;
}

if(count == 2) cout<<" YES "<<endl; else cout<<"NO "<<endl;

return 0;
}

in C++ code

bool concatenateString(string strs[], int n)
{
	int tail[26]={0};
	int count = 0;
	for(int i = 0; i < n; i++)
	{
		tail[strs[i][strs[i].size()-1]-'a']++;
		tail[strs[i][0]-'a']--;
	}
	for(int i = 0; i < 26; i++)
	{
		count += abs(tail[i]);
	}
	if(count == 2)
		return true;
	else
		return false;
}

The basic idea is keep two list,
src and dest.
- when you need to check whether to put current Scr in srcList, check if previous any one of destinations is same as that of curSrc then remove that from destList and don't put current scr into srcList.
- Similarly for current dest.

At the end you should have only one source.

public static boolean isChained(String [] words) {
	    
	    ArrayList<Character> src = new ArrayList<Character>();
	    ArrayList<Character> dest = new ArrayList<Character>();
	    int i;
	    int n = words.length;
	    boolean putSrc = false;
	    boolean putDest = false;
	    for(i=0; i<n; i++) {
	        String str = words[i];
	        Character s = str.charAt(0);
	        Character e = str.charAt(str.length()-1);
	        if(dest.contains(s)) {
	        	putSrc = false;
	        	dest.remove(s);
	        } else {
	        	putSrc = true;
	        }
	        
	        if(src.contains(e)) {
	        	putDest = false;
	        	src.remove(e);
	        } else {
	        	putDest = true;
	        }
	        
	        if(putSrc)
	        	src.add(s);
	        if(putDest)
	        	dest.add(e);
	    }
	    
	    if(src.size() == 1) {
	        return true;
	    } else {
	        return false;
	    }
	}

Can we create an array of 26 length? Initialize all elements to null. Then iterate through each string, setting the array as follows:
first look at string[0]. Compare to string[len(string)-1]. They can be equal or not equal.
1. If equal: set array[f(string[0])]=MAXINT but only if array[f(string[0])]==NULL, otherwise skip this string.
f(X)=numeric place of X in the alphabet e.g.A=1,B=2, etc.
2. If not equal:
a. If array[f(string[0])==NULL or MAXINT, set it to 1.
b. Otherwise, increment it.
c. Perform same test on array[f(string[len(string)-1])] but decrement instead of increment.
When we are done we iterate through the 26-element array.
-If we see any element with value >1 or <-1, return false.
-Else if we count more than one element with 1 or -1, also return false.
-Else return true.
This should be O(N) complexity, no?

To solve this problem, you need to know SCC(strongly connected components) at first.
Just build the directed graph as many guys said before, then combinate every circles(SCC) into a node one by one, then check whether the final graph is a single link.
Time: O(N) Space: O(N)

My God. I cannot believe so many people mention Hamilton circle. What are you thinking? Here is a case: Three words, sag,gs,sk. They can be chained as sagsk. If we build a graph, node s is visited more than once. Thus it's Eulerian path in a directed graph. There is another similar question on geeksforgeeks " given-array-strings-find-strings-can-chained-form-circle/ “

// works only when the first and last chars are not duplicated in words
// i.e. abcd, aefg are not working on this code since there are two a's

import java.util.*;

public class ChainOfStringsUsingMaps {

public static boolean chainableString( List<String> words ) {
Map<Character, Character> map = new HashMap<Character, Character>();

for( String word : words ) {
char[] S = word.toCharArray();
char f = S[0];
char l = S[S.length-1];

map.put( f, l );
}

Set<Character> visited = new HashSet<Character>();
List<Character> list = new LinkedList<Character>();

int count = 1;

for( Map.Entry<Character, Character> entry : map.entrySet() ) {
Character first = entry.getKey(); // key = first char
Character last = entry.getValue(); // val = last char

if( map.containsKey(last) && !visited.contains(last) ) {
list.add(last);
visited.add(last);
count = count*2;
}
}

if( list.size()*2 == map.size()*2 - 2) return true;
else return false;
}

public static void main(String[] args) {
List<String> stringList1 = new ArrayList<String>();
stringList1.add("sdfg");
stringList1.add("dfgs");
stringList1.add("ghjhk");

System.out.println( chainableString( stringList1));

List<String> stringList2 = new ArrayList<String>();
String dict[] ={"sdfg", "ydfgfx", "dfgs", "nertty", "ghjhn"};
for(String word : dict )
stringList2.add(word);

System.out.println( chainableString( stringList2));

}

}

// works only when the first and last chars are not duplicated in words
// i.e. abcd, aefg are not working on this code since there are two a's 

import java.util.*;

public class ChainOfStringsUsingMaps {
	
	public static boolean chainableString( List<String> words ) {
		Map<Character, Character> map = new HashMap<Character, Character>();
		
		for( String word : words ) {
			char[] S = word.toCharArray();
			char f = S[0];
			char l = S[S.length-1];

			map.put( f, l );
		}

		Set<Character> visited = new HashSet<Character>();
		List<Character> list = new LinkedList<Character>();

		int count = 1;

		for( Map.Entry<Character, Character> entry : map.entrySet() ) {
			Character first = entry.getKey();			// key = first char
			Character last = entry.getValue();		// val = last char

			if( map.containsKey(last) && !visited.contains(last) ) {
				list.add(last);
				visited.add(last);
				count = count*2;
			}
		}

		if( list.size()*2 == map.size()*2 - 2) return true;
		else return false;
	}

    public static void main(String[] args) {
       List<String> stringList1 = new ArrayList<String>();
        stringList1.add("sdfg");
        stringList1.add("dfgs");
        stringList1.add("ghjhk");

        System.out.println( chainableString( stringList1));

       	List<String> stringList2 = new ArrayList<String>();
        String dict[] ={"sdfg", "ydfgfx", "dfgs", "nertty", "ghjhn"};
        for(String word : dict )
        	stringList2.add(word);

        System.out.println( chainableString( stringList2));

    }

}

1) Consider all ending and initial character as vertices of graph.
2)string as edge.
3) Form a directed graph
4) find "Euler path"
i) if path found concatenation all string in path.
ii) else no chain possible

eg:
1) a...d
2) q...b
3) n...f
4) a...q
5) f...a
6) d....n

Nodes will be: a b d n f q

Edged will be: 1) a->d 2) q->b 3) n->f 4)a->q 5)f->a 6)d->n

One possible path will be:
a->d->n->f->a->q->b

so chain will be:
a...d...n...f...a...q...b

THis problem can be solved by using topological sorting. We need to build a directed graph, where each node corresponds to either 1st or last char of string.

Assume 1st char of a string is directed to last char of same string, And in the beginning graph does not have any nodes.

Traverse from 1st string.
1. Take 1st string. Build a graph where 1st and last char will represent two nodes, pointing from 1st to last char.
2. Take 2nd string. If 1st char of this string exists in a graph, then add last char of this string as a node in the graph. Else, build one more graph, the way we built in step 1. Here we have two disconnected graphs.
3. Take 3rd string. If 1st char of this string exists in graphs, then check if last char exists. If it exists, then connect these two nodes. Else, add last char of this string as a node in the graph, else build one more disconnected graph.

Say, we have,
first string=sdfg
second string=ydfgfx
third string=dfgs
fourth string=nertty
fifth string=ghjhn

from 1st string = [s]-->[g] (1st graph)
from 2nd string = [y]-->[x] (2nd graph)
from 3rd string = [d]-->[s]-->g ( Since, 's' is already in 1st graph, connect 3rd string to 1st string)
from 4th string = [n]-->[y]-->x ( Since, 'y' is already in 2nd graph, connect 4th string to 2nd string)
from 5th string = d-->s-->[g]-->[n]-->y-->x (Since, 1st char 'g' is in 1st graph, and last char 'n' is in 2nd graph, so connect these two graphs)

Now, we can check if there is more than one connected graphs using DFS. A chain can be formed if there is only one graph.
In above scenario, a chain can be formed.

Form a Bipartite graph having the starting characters of the strings in one group and ending characters in the other group. Create two hash maps one will contain starting characters and other will contain ending characters. while inserting a starting character or ending character of a string in the hashmap check whether the character is already in the other hashmap. If yes then connect an edge between the corresponding nodes in the Graph. In the graph each source node is connected to its corresponding end node.
Now if the graph contains more than one node with in degree 0 then Its NOT POSSIBLE to form the chain. If the graph contains only one node with in degree 0 and if it has only one component then its possible to form a chain.

1. Create directed graph from strings.
dfgs -> sdfg -> ghjhk
This graph could be complex with cycles.
2. Check if directed graph has Euler path/cycle.

2.1. A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
2.2. A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).

public static boolean canChain(String[] strs) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() < 2 || strs[i].charAt(0) == strs[i].charAt(strs[i]
.length() - 1))
continue;
if (map.containsKey(strs[i].charAt(0))) {
map.remove(strs[i].charAt(0));
} else {
map.put(strs[i].charAt(0), i);
}
if (map.containsKey(strs[i].charAt(strs[i].length() - 1))) {
map.remove(strs[i].charAt(strs[i].length() - 1));
} else {
map.put(strs[i].charAt(strs[i].length() - 1), i);
}
}

if (map.size() == 0 || map.size() == 2)
return true;
return false;
}

In this program i am populating map and array of strings manually.
And considering all N no of strings are unique.


public class Chain
{


public static void main(String a[])
{

Map<String,String> map=new HashMap<String,String>();
map.put("a","abc");
map.put("d","def");
map.put("c","cod");
map.put("g","geb");
map.put("b","bea");

String[] arr=new String[5];
arr[0]="abc";
arr[1]="def";
arr[2]="cod";
arr[3]="geb";
arr[4]="bea";

int i=0;
String temp;
int count=0;
while((arr.length)!=i)
{
StringBuilder sb=new StringBuilder();
temp=arr[i];
sb.append(temp);
count=0;
while(true)
{
if(map.get(temp.substring(temp.length()-1))!=null)
{
temp=map.get(temp.substring(temp.length()-1));
sb.append(temp);
count++;
}
else
{
if(count!=(arr.length-1))
{
break;
}
else
{
System.out.println("Chain Found: "+sb.toString());
break;
}
}
}

if(count==(arr.length-1))
{
break;
}
i++;

if((arr.length)==i)
{
System.out.println("Chain not Found");
}
}

}
}

public boolean isChain(ArrayList<String> p_list){
        int index;
        index = 0;
        String firstword,secondword;
        
        while(index < (p_list.size()-1)){
            firstword = p_list.get(index);
            secondword = p_list.get(index+1);
            if( (firstword.charAt(firstword.length()-1)) !=
                    secondword.charAt(0)){
                return false;
            }
            index++;
            
        }
        
       
        return true;
    }

the way i understand the question is that you need to only compare the neighboring strings. so i will compare the last character in first string and first character in next string and so on will moving along the list and that will be O(n). if we are only interested in the answer to the question can a chain be formed then returning a boolean seems sufficient.

1. First make permutation of three string.
2. Before concatenation check last char of first is same as first char of second.
3. Make 2nd step for all three string(In this case we have three String.)
4. Return appropriate concatenated string if satisfying step 2.

It seems to me like that giving the full concatenated String is not necessary. What is needed is to answer if a chain is possible given a list of Strings.

Methodology:
Iterate over words and store the first and the last chars in two maps Map<Character, Integer>
If the two maps have the same first and last chars count then they can match.
Note that we can tolerate up to 1 difference. (The first/last char of the final String is not connected with any).

Code:

public boolean concatAll (String[] words){
    Map<Character, Integer> firstsMap = new HashMap<Character, Integer>();
    Map<Character, Integer> endingMap = new HashMap<Character, Integer>();

  
	//populate maps
    for (String s : words)
    {
        //assume that empty characters are always attachable
        if (s.equals(""))
            continue;

        char beginChar = s.charAt(0);
        addToMap(firstsMap, beginChar);
        char lastChar = s.charAt(s.length()-1);
        addToMap(endingMap, lastChar);
    }

    int notMatching=0;
    for (Entry<Character, Integer> e : firstsMap.entrySet()){
        Integer firstCount = e.getValue();
        if (notMatching>1)
            return false;
        Integer endingCount = endingMap.get(e.getKey());
        if (endingCount!=null){
            if (!(firstCount == endingCount))
                notMatching+=Math.abs(endingCount-firstCount);
        }
        else
        {
            notMatching+=firstCount;
        }
    }

    if (notMatching>1)
        return false;

    return true;

}

private void addToMap(Map<Character, Integer> map, char c){
    Integer i = map.get(c);
    if (i==null)
        i=0;

    map.put(c, i+1);
}

EDIT: Time Complexity O(n) where n the number of words in the array.