首页 > 试题广场 >

最大字母矩阵

[编程题]最大字母矩阵

热度指数：2382 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string数组dic，代表单词列表，同时给定列表的长度n，请返回最大子矩阵的面积，其中子矩阵中的行和列相同，且有相同字母组成。保证单词的大小小于等于50，且某一长度的串的数量小于等于12。

测试样例：

["aaa","aaa","aaa","bb","bb"]

返回：9

算法知识视频讲解

王六六

是我语文太差了吗(按别人的代码写的答案，题没看懂。）

class AlphaMatrix:
    def findAlphaMatrix(self, dic, n):
        # write code here
        from collections import Counter
        rec=Counter(dic)
        ans=0
        for k in rec:
            ans=max(ans,rec[k]*len(k))
        return ans

编辑于 2019-06-28 19:13:18 回复(0)

更多回答

joc

感觉题目说的不太清楚，测试用例也有点单一

发表于 2016-05-10 13:01:27 回复(3)

C/C++

codewind

#define max(i,j)  i>j ? i: j
class AlphaMatrix {
public:
    
    int findAlphaMatrix(vector<string> dic, int n) {
        // write code here
        unordered_map<string,int> height;
        int res=0;
        for(string &x : dic) {
            height[x]++;
            res = max(res, height[x]*x.size());
        }
        return res;
    }
};

发表于 2021-04-07 10:16:45 回复(2)

jiangcw

//game over

import java.util.*;

public class AlphaMatrix {
    public int findAlphaMatrix(String[] dic, int n) {
        // write code here
        if(n < 1)
            return 0;
        int res = 0;
        HashMap<String,Integer> map = new HashMap<>();
        for(int i = 0; i < n ; i++) {
            if(map.containsKey(dic[i])) {
                map.put(dic[i], map.get(dic[i]) + 1);
                res = Math.max(res, map.get(dic[i]) * dic[i].length());
            }else {
                map.put(dic[i], 1);
                res = Math.max(res, dic[i].length());
            }
        }
        return res;
    }
}

发表于 2017-06-11 17:15:34 回复(0)

-狂战-

//利用HashMap中键的唯一性
import java.util.*;

public class AlphaMatrix {
    public int findAlphaMatrix(String[] dic, int n) {
        
        int result = 0;
        HashMap<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<dic.length; i++){
            if(!map.containsKey(dic[i])) map.put(dic[i], 1);
            else map.put(dic[i], map.get(dic[i])+1);
        }
        
        for(int i=0; i<dic.length; i++) 
            result = Math.max(result, map.get(dic[i])*dic[i].length());

       return result; 
    }
}

/*吐槽：你在测试用例里加个中文逗号，eclipse都编译不了，你让我怎么通过，不带这么欺负人的 case通过率为96.77% 测试用例: ["abcdef"，"abcdef","abcdef","aaa","ccc","ddd","eee","fff"],8 对应输出应该为: 18 你的输出为: 15 */

编辑于 2020-09-23 18:32:29 回复(2)

C/C++

nbgao

class AlphaMatrix {
public:
    int findAlphaMatrix(vector<string> dic, int n) {
        if(n<1)
            return 0;         
      int Max = 0;         
      map<string,int> m;         
      for(int i=0;i<n;i++){             
      int l = dic[i].length();             
      if(m.find(dic[i]) != m.end()){                 
      m[dic[i]]++;                 
      Max = max(Max, l*m[dic[i]]);             
      }else{                 
      m[dic[i]] = 1;                 
      Max = max(Max, l*m[dic[i]]);             
      }         
      }         
      return Max;
    }
};

编辑于 2020-09-23 18:33:06 回复(0)

EmmaLR

这道题，我想的太复杂了，本来想排序后统计相同的字符组成的最大面积，类似于求最大子方阵，想利用动态规划求解，但是在写的过程中发现，若字符串长度不同，还需要进行处理。。。。。

此处省略一万字，我没写出来。

后来翻看大家的讨论，发现这道题需要完全相同的单词才可以，而且要求串的长度相同，所以参照

的方法，写出来一个答案。。。。

class AlphaMatrix {
public:
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    int findAlphaMatrix(vector<string> dic, int n) {
        // write code here
      	int res=0;
        map<string,int> tmp;
        
        for(int i=0;i<n;i++)
        {
            tmp[dic[i]]++;
            int curArea=dic[i].length()*tmp[dic[i]];
            res=max(curArea,res);
        }
        
        return res;
    }
};

发表于 2017-05-24 17:10:41 回复(0)

Aurora1

class AlphaMatrix:
    def findAlphaMatrix(self, dic, n):
        for x in dic:
            k = len(x)
            if k in self.d:
                self.d[k].append(x)
            else:
                self.d[k] = [x]
        l = max(self.d.keys())
        for z in xrange(l * l, -1, -1):
            for i in xrange(1, l + 1):
                if z % i == 0:
                    j = z / i
                    if j <= l and (i in self.d and j in self.d):
                        if j not in self.m:
                            self.m[j] = Node(self.d.get(j, []))  # 构建字典树
                        tree = self.m[j]
                        if self.makeRect(i, j, [], tree) is not None:
                            return z
        return 0

    def __init__(self):
        self.d = {}  # 长度->字符串序列
        self.m = {}  # 长度->字典树

    def makeRect(self, w, h, A, tree):
        if len(A) == h:
            return A
        for x in self.d[w]:
            B = list(A)
            B.append(x)
            if self.checkRow(w, B, tree): #检查列单词是否在字典树里
                t = self.makeRect(w, h, B, tree)
                if t:
                    return t

    def checkRow(self, w, A, tree):
        for i in range(w):
            d = []
            for j in range(len(A)):
                d.append(A[j][i])
            if not tree.exist(d):
                return False
        return True


class Node():  # Trie树
    def __init__(self, arrStr=[]):
        self.child = {}  # 字母->子节点
        for str in arrStr:
            self.insert(str)

    def insert(self, str):
        p = self
        for c in str:
            if c not in p.child:
                p.child[c] = Node()
            p = p.child[c]

    def exist(self, d):  # 检查单词是否是该字典树的前缀
        p = self
        for c in d:
            if c not in p.child:
                return False
            p = p.child[c]
        return True

发表于 2017-03-24 14:16:52 回复(0)

牛客137339号

做完了牛客的金典，发现整体出题的质量不高，感觉这个模块的程序猿和offer的根本就不是一个水平，起码态度就不好，很多题，弄的题意很不明确，把人家原书的题改的乱七八糟的。

发表于 2016-08-27 17:37:24 回复(4)

奥利给任一一

class AlphaMatrix:
    def findAlphaMatrix(self, dic, n):
        count = {}
        for i in set(dic):
            count[i] = dic.count(i)
        res = 0
        for l in count:
            res = max(res, len(l)*count[l])
        return res

发表于 2020-08-12 10:33:16 回复(0)

Java

我是ben啊

这题目把我看蒙了，我想了很多，比如{abcd,abcd,abcd,abcd,aa,bb,cc,dd}最大是8还是16.。。。我看了题解后才发现题目的意思是找重复单词构成的最大矩阵面积。

//能够组成矩阵的必定是单词一样的
	 public int findAlphaMatrix(String[] dic, int n) {
	        // write code here
		 //利用hashmap统计重复单词数，再从中挑出能组成矩阵的最大值
		 Map<String, Integer> hash=new HashMap<String, Integer>();
		 int Max=Integer.MIN_VALUE;
		 for (int i = 0; i < n; i++) {
			if (hash.containsKey(dic[i])) {
				hash.put(dic[i], hash.get(dic[i])+1);
			}else {
				hash.put(dic[i], 1);
			}
			Max=Math.max(Max,dic[i].length()*hash.get(dic[i]) );
		}
		 return Max;
	    }

发表于 2020-06-18 15:27:10 回复(0)

白色纯度

不推荐这个模块，好好把剑指offer 和 17年，18年或19年的校招真题好好刷就行。做这个基本是浪费时间，银行的机考水平，去互联网的话这些题不够看。

发表于 2019-09-01 09:02:48 回复(0)

~~好好工作~~

这哪里是DP啊

import java.util.*;

public class AlphaMatrix {
    public int findAlphaMatrix(String[] dic, int n) {
        HashMap<String, Integer> set = new HashMap<>();
        for (int i = 0;i < dic.length; ++ i)
            set.put(dic[i], set.containsKey(dic[i]) ? set.get(dic[i]) + 1 : 1);
        int max = -1;
        for (String s : set.keySet()){
            if (set.get(s) * s.length() > max){
                max = set.get(s) * s.length();
            }
        }
        return max;
    }
}

编辑于 2019-07-29 10:08:54 回复(0)

C/C++

Salmon-William

//题目表述的真是一点都不清晰啊，就是找出现次数最多的那个单词，然后面积就是
//这个单词出现的次数*单词长度
class AlphaMatrix {
public:
    int findAlphaMatrix(vector<string> dic, int n) {
        map<string,int> mapp;
        int res=0;
        for(int i=0;i<n;i++)
            {
            mapp[dic[i]]++;
            int t=dic[i].length()*mapp[dic[i]];
            res=max(res,t);
        }
        return res;
    }
};

发表于 2017-10-06 10:54:47 回复(0)

C/C++

cxxxxxxxy

//用map去统计每个单词的出现的次数，次数相当于矩阵的列，而单词长度相当于矩阵的行！

class AlphaMatrix {

public:

int findAlphaMatrix(vector<string> dic, int n) {

// write code here

map<string,int> m;

for(int i=0;i<n;i++){

if(m.find(dic[i])!=m.end())

m[dic[i]]+=dic[i].size();

else

m[dic[i]]=dic[i].size();

}

int max=0;

map<string,int>::iterator iter=m.begin();

for(;iter!=m.end();iter++)

{

if(max<iter->second)

max=iter->second;

}

return max;

}

};

发表于 2017-05-17 23:10:42 回复(0)

小红gfgf

测试用例:
["abcdef","abcdef","abcdef","aaa","ccc","ddd","eee","fff"],8

对应输出应该为:

18

你的输出为:

9

这个测试用例的输出为什么是18？

按照题目的意思，矩阵

abcdef

是不满足的啊！因为数组中没有"bbb"！！！

发表于 2017-04-05 22:54:40 回复(0)

alicehua

采用动态规划，用数组arr记录下从第一个字符串到当前字符串中最短子串，如果当前串的长度和前一个串的长度不等，则计数器flag定位为当前串位置，对应的子矩阵长度为（i-flag+i)*arr[i]，其实刚开始以为结果为从第一个串到当前串的个数*arr[i]，但运行后发现要等长的才能计算在内。应该还可以优化一下代码的但是，这个程序可能可以体现我的思路吧

import java.util.*;

public class AlphaMatrix {

public int findAlphaMatrix(String[] dic, int n) {

// write code here

int max =0;

int[] arr = new int[n];

arr[0] = max(1,dic[0].length());

int flag =0;

for(int i=1;i<n;i++){

int len = dic[i].length();

arr[i] = min(arr[i-1],len);

if(len != arr[i-1])

flag = i;

int temp = arr[i]*(i-flag+1);

if(max<temp)

max = temp;

}

return max;

}

public int max(int a,int b){

return a>b?a:b;

}

public int min(int a,int b){

return a<b?a:b;

}

发表于 2016-10-10 08:30:05 回复(0)

Hester_Wang

public int findAlphaMatrix(String[] dic, int n) {
		int[] rows = new int[n];
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++)
			rows[i] = dic[i].length();
		for (int i = 1; i < n; i++) {
			if (dic[i].equals(dic[i-1]))
				rows[i] += rows[i - 1];
			max = Math.max(max, rows[i]);
		}

		return Math.max(max, rows[0]);
	}  //1、建立一个数组rows[n]，存放每个字符串的长度 
//2、从1--n-1,判断相邻两个字符串是否相等,若相等，更新rows[i]=rows[i-1]+rows[i],否则，rows[i]为该字串的长度，不变 
//3、最大字母矩阵面积即为max（rows[i]）(i=0,,,n-1);

编辑于 2016-10-08 19:30:06 回复(0)

mirandac

class AlphaMatrix:

def findAlphaMatrix(self, dic, n):

# write code here

dic=list(set(dic))

dic.sort(key=len,reverse=True)

strSet=set(dic)

lengths=list(set(map(len,dic)))

lengths.sort(reverse=True)

for ll in lengths:

currentDic=[string for string in dic if len(string)==ll]

for ii in dic:

flag=0

mats=[[]]

for index in range(len(ii)):

a=ii[index]

starts=[string for string in currentDic if string[0]==a ]

if not starts:

flag=1

break

mats=[mat+[t] for mat in mats for t in starts]

print mats

if flag==1:

continue

for mm in mats:

matStrings=[]

for k in range(ll):

a=''.join( [mm[s][k] for s in range(len(mm))])

if ll==9:

pass

matStrings.append(a)

strSet1=set(matStrings)

if strSet1<=strSet:

return ll*len(ii)

        return 0

发表于 2016-10-07 23:01:19 回复(0)

零时半雨

题目说得不清楚啊，试过之后，发现是需要完全相同的单词才行，而串长度相同，串不一样也不行。
为了方便，使用了map。
class AlphaMatrix {
public:
    int findAlphaMatrix(vector<string> dic, int n) {
        int i=0;
        map<string,int> count;
        int m=0;
        for(i=0;i<n;i++)
        {
             count[dic[i]]++;    
            if(count[dic[i]]*dic[i].length()>m)
                {
                m=count[dic[i]]*dic[i].length();
                }
        }
        return m;
        
    }
};

发表于 2016-08-26 17:51:29 回复(0)